中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置： 首頁 > news >正文

青島專業(yè)網(wǎng)站制作團(tuán)隊(duì)肇慶百度快照優(yōu)化

news 2025/7/5 18:30:27
青島專業(yè)網(wǎng)站制作團(tuán)隊(duì),肇慶百度快照優(yōu)化,哪個(gè)網(wǎng)站能上傳自己做的簡(jiǎn)歷,網(wǎng)站開發(fā) 后端服務(wù)目錄 二分查找算法原理 ①力扣704. 二分查找 解析代碼 ②力扣34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 解析代碼 ③力扣69. x 的平方根 解析代碼 ④力扣35. 搜索插入位置 解析代碼 ⑤力扣852. 山脈數(shù)組的峰頂索引 解析代碼 ⑥力扣162. 尋找峰值 解析代碼…

目錄

二分查找算法原理

①力扣704. 二分查找

解析代碼

②力扣34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

解析代碼

③力扣69. x 的平方根?

解析代碼

④力扣35. 搜索插入位置

解析代碼

⑤力扣852. 山脈數(shù)組的峰頂索引

解析代碼

⑥力扣162. 尋找峰值

解析代碼

⑦力扣153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值

解析代碼

⑧力扣LCR 173. 點(diǎn)名

解析代碼

本篇完。

二分查找算法原理

????????二分查找一種效率較高的查找方法。已經(jīng)有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明其時(shí)間復(fù)雜度是O（logN），如果在全國(guó)14億人口中找一個(gè)人，那么只需查找31次，但是，二分查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列（無序有時(shí)也行，但是要有二段性）。一般步驟如下：

????????首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

以前學(xué)C/C++也寫過二分查找的代碼，直接刷題：

①力扣704. 二分查找

704. 二分查找 - 力扣（LeetCode）

難度 簡(jiǎn)單

給定一個(gè)?n?個(gè)元素有序的（升序）整型數(shù)組?nums?和一個(gè)目標(biāo)值?target??，寫一個(gè)函數(shù)搜索?nums?中的?target，如果目標(biāo)值存在返回下標(biāo)，否則返回?-1。
示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

示例?2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假設(shè)?nums?中的所有元素是不重復(fù)的。
  2. n?將在?[1, 10000]之間。
  3. nums?的每個(gè)元素都將在?[-9999, 9999]之間。
class Solution {
public:int search(vector<int>& nums, int target) {}
};

解析代碼

首先是有序的，就知道用二分，且這是一道樸素的二分（后面有不樸素的），簡(jiǎn)單題重拳出擊：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
};

②力扣34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 - 力扣（LeetCode）

難度 中等

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個(gè)目標(biāo)值?target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值?target，返回?[-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

  • 0 <= nums.length <= 10^5
  • -10^9?<= nums[i]?<= 10^9
  • nums?是一個(gè)非遞減數(shù)組
  • -10^9?<= target?<= 10^9
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {}
};

解析代碼

非遞減，就是數(shù)組往后都是大于或者等于的元素，用暴力解法就是找到隨便一個(gè)端點(diǎn)元素，然后往前往后線性遍歷，極端時(shí)間復(fù)雜度還是O（N），這里用進(jìn)階二分的套路（等下總結(jié)）

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int size = nums.size();if(size == 0) // 處理邊界return {-1, -1}; //返回一個(gè)vector里兩個(gè)整數(shù)的方式int left = 0, right = size - 1; // 找左端點(diǎn)while(left < right) // 一定是小于{int mid = left + (right - left) / 2; // 元素個(gè)數(shù)是偶數(shù)時(shí)，中點(diǎn)是中間的左邊if(nums[mid] < target) // 左端點(diǎn)肯定不在左邊left = mid + 1;elseright = mid; // 可能自己是左端點(diǎn)，可能左端點(diǎn)還在左邊}if(nums[left] != target) // 沒有端點(diǎn)的情況return {-1, -1};int tmp = left; // 記錄左端點(diǎn)right = size - 1; // 找右端點(diǎn)，left不用重置while(left < right){int mid = left + (right - left + 1) / 2; // 元素個(gè)數(shù)是偶數(shù)時(shí)，中點(diǎn)是中間的右邊if(nums[mid] > target) // 右端點(diǎn)肯定右在左邊right = mid -1;elseleft = mid; // 可能自己是右端點(diǎn)，可能右端點(diǎn)還在右邊}return {tmp, right};}
};

以后二分大部分題目都是這個(gè)進(jìn)階二分的套路，套路就是這樣的了（注意兩個(gè)while的比較）：

        int left = 0, right = size - 1; // 找左端點(diǎn)while(left < right) // 一定是小于{int mid = left + (right - left) / 2; // 元素個(gè)數(shù)是偶數(shù)時(shí)，中點(diǎn)是中間的左邊if(nums[mid] < target) // 左端點(diǎn)肯定不在左邊left = mid + 1;elseright = mid; // 可能自己是左端點(diǎn)，可能左端點(diǎn)還在左邊}if(nums[left] != target) // 沒有端點(diǎn)的情況return {-1, -1};int tmp = left; // 記錄左端點(diǎn)right = size - 1; // 找右端點(diǎn)，left不用重置while(left < right){int mid = left + (right - left + 1) / 2; // 元素個(gè)數(shù)是偶數(shù)時(shí)，中點(diǎn)是中間的右邊if(nums[mid] > target) // 右端點(diǎn)肯定右在左邊right = mid -1;elseleft = mid; // 可能自己是右端點(diǎn)，可能右端點(diǎn)還在右邊}return {tmp, right};

③力扣69. x 的平方根?

69. x 的平方根 - 力扣（LeetCode）

難度 簡(jiǎn)單

給你一個(gè)非負(fù)整數(shù)?x?，計(jì)算并返回?x?的?算術(shù)平方根?。

由于返回類型是整數(shù)，結(jié)果只保留?整數(shù)部分?，小數(shù)部分將被?舍去 。

注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。

示例 1：

輸入：x = 4
輸出：2

示例 2：

輸入：x = 8
輸出：2
解釋：8 的算術(shù)平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

提示：

  • 0 <= x <= 2^31 - 1
class Solution {
public:int mySqrt(int x) {}
};

解析代碼

暴力解法可以遍歷1到X / 2的所有整數(shù)，因?yàn)檫@段整數(shù)是有序的，所有可以用二分算法，用上一題力扣34總結(jié)的進(jìn)階二分套路，求右端點(diǎn)：

class Solution {
public:int mySqrt(int x) {if(x <= 1) // 看給的范圍處理邊界{return x / 1; // 如果是1的話下面right就是0了}int left = 0, right = x / 2;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid > x) // 開long long防溢出{right = mid - 1;}else{left = mid;}}return right;}
};

④力扣35. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

難度 簡(jiǎn)單

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請(qǐng)必須使用時(shí)間復(fù)雜度為?O(log n)?的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums?為?無重復(fù)元素?的?升序?排列數(shù)組
  • -10^4 <= target <= 10^4
class Solution {
public:int searchInsert(vector<int>& nums, int target) {}
};

解析代碼

明顯的二分查找，且找左端點(diǎn)：

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;if(nums[right] < target) // 找不到就尾插{return right + 1;}while(left < right) // 找不到target就找一個(gè)比target大的值，插入到它的前面{int mid = left + (right - left) / 2; // 根據(jù)上面注釋用二分中找左端點(diǎn)的套路if(nums[mid] < target){left = mid + 1;}else{right = mid;}}return left; // 找沒找到都是返回left下標(biāo)}
};

⑤力扣852. 山脈數(shù)組的峰頂索引

852. 山脈數(shù)組的峰頂索引 - 力扣（LeetCode）

LCR 069. 山脈數(shù)組的峰頂索引 - 力扣（LeetCode）

難度 中等

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請(qǐng)必須使用時(shí)間復(fù)雜度為?O(log n)?的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums?為?無重復(fù)元素?的?升序?排列數(shù)組
  • -10^4 <= target <= 10^4
class Solution {
public:int searchInsert(vector<int>& nums, int target) {}
};

解析代碼

雖然整個(gè)數(shù)組不是有序的，但是根據(jù)單調(diào)性可以分出二段性。這里利用二段性把mid歸到遞增部分，下面就是找右端點(diǎn)：

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {// 雖然整個(gè)數(shù)組不是有序的，但是根據(jù)單調(diào)性可以分出二段性// 這里利用二段性把mid歸到遞增部分，下面就是找右端點(diǎn)：int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] < arr[mid - 1]) // 如果是遞減部分{right = mid - 1;}else{left = mid;}}return left;}
};

⑥力扣162. 尋找峰值

162. 尋找峰值 - 力扣（LeetCode）

難度 中等

峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。

給你一個(gè)整數(shù)數(shù)組?nums，找到峰值元素并返回其索引。數(shù)組可能包含多個(gè)峰值，在這種情況下，返回?任何一個(gè)峰值?所在位置即可。

你可以假設(shè)?nums[-1] = nums[n] = -∞?。

你必須實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法來解決此問題。

示例 1：

輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2。

示例?2：

輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5 
解釋：你的函數(shù)可以返回索引 1，其峰值元素為 2；或者返回索引 5， 其峰值元素為 6。

提示：

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
class Solution {
public:int findPeakElement(vector<int>& nums) {}
};

解析代碼

????????注意到是返回任意個(gè)峰值都可以，就類似數(shù)學(xué)的求極大值，那問題就變成上一題力扣852. 山脈數(shù)組的峰頂索引了，直接把nums參數(shù)改成arr然后復(fù)制上一題代碼過來就AC了，二段性就是如果找到一個(gè)點(diǎn)，如果這個(gè)點(diǎn)的右邊元素比它小，那么一定有一個(gè)極大值在它左邊。反之極大值在它右邊或者它就是極大值。

class Solution {
public:int findPeakElement(vector<int>& arr) {// 雖然整個(gè)數(shù)組不是有序的，但是根據(jù)單調(diào)性可以分出二段性// 這里利用二段性把mid歸到遞增部分，下面就是找右端點(diǎn)：int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] < arr[mid - 1]) // 如果是遞減部分{right = mid - 1;}else{left = mid;}}return left;}
};

⑦力扣153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值

153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 - 力扣（LeetCode）

難度 中等

已知一個(gè)長(zhǎng)度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。例如，原數(shù)組?nums = [0,1,2,4,5,6,7]?在變化后可能得到：

  • 若旋轉(zhuǎn)?4?次，則可以得到?[4,5,6,7,0,1,2]
  • 若旋轉(zhuǎn)?7?次，則可以得到?[0,1,2,4,5,6,7]

注意，數(shù)組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉(zhuǎn)一次?的結(jié)果為數(shù)組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個(gè)元素值?互不相同?的數(shù)組?nums?，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請(qǐng)你找出并返回?cái)?shù)組中的?最小元素?。

你必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數(shù)組為 [1,2,3,4,5] ，旋轉(zhuǎn) 3 次得到輸入數(shù)組。

示例 2：

輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數(shù)組為 [0,1,2,4,5,6,7] ，旋轉(zhuǎn) 3 次得到輸入數(shù)組。

示例 3：

輸入：nums = [11,13,15,17]
輸出：11
解釋：原數(shù)組為 [11,13,15,17] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums?中的所有整數(shù)?互不相同
  • nums?原來是一個(gè)升序排序的數(shù)組，并進(jìn)行了?1?至?n?次旋轉(zhuǎn)
class Solution {
public:int findMin(vector<int>& nums) {}
};

解析代碼

?二段性就是以最右邊元素（下圖為D）為標(biāo)志，如果一個(gè)點(diǎn)比它大，那么找的元素肯定在另一邊，

以A為標(biāo)志也行，但是有邊界情況要處理，下面就以D為標(biāo)志，找左端點(diǎn)：

class Solution {
public:int findMin(vector<int>& nums) {// 二段性就是以最右邊元素為標(biāo)志，如果一個(gè)點(diǎn)比它大，那么找的元素肯定在另一邊// 以下就是二分找左端點(diǎn)的套路int left = 0, right = nums.size() - 1;int tmp = right;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[tmp]) // 如果是遞減部分{left = mid + 1;}else{right = mid;}}return nums[left];}
};

⑧力扣LCR 173. 點(diǎn)名

LCR 173. 點(diǎn)名 - 力扣（LeetCode）

難度 簡(jiǎn)單

某班級(jí) n 位同學(xué)的學(xué)號(hào)為 0 ~ n-1。點(diǎn)名結(jié)果記錄于升序數(shù)組?records。假定僅有一位同學(xué)缺席，請(qǐng)返回他的學(xué)號(hào)。

示例 1:

輸入: records = [0,1,2,3,5]
輸出: 4

示例?2:

輸入: records = [0, 1, 2, 3, 4, 5, 6, 8]
輸出: 7

提示：

1 <= records.length?<= 10000

class Solution {
public:int takeAttendance(vector<int>& records) {}
};

解析代碼

此題就是以前寫過的劍指Offer中數(shù)組消失的數(shù)字，解法有哈希，遍歷，位運(yùn)算，數(shù)學(xué)求和，時(shí)間都是O（N），二分的解法是O（logN）。

二段性就是找的元素的值肯定不等于數(shù)組下標(biāo)，求左端點(diǎn)的套路：

class Solution {
public:int takeAttendance(vector<int>& records) {// 解法有哈希，遍歷，位運(yùn)算，數(shù)學(xué)求和，時(shí)間都是O（N），二分的解法是O（logN）// 此題二段性就是找的元素的值肯定不等于數(shù)組下標(biāo)，求左端點(diǎn)的套路int left = 0, right = records.size() - 1;if(records[right] == right){return right + 1;}while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid){left = mid + 1;}else{right = mid;}}return records[left] - 1;}
};

本篇完。

下一部分是前綴和算法。

http://www.risenshineclean.com/news/34449.html

相關(guān)文章：

  • 做宣傳圖冊(cè)在什么網(wǎng)站外國(guó)黃岡網(wǎng)站推廣平臺(tái)
  • 做潤(rùn)滑油網(wǎng)站圖片直播回放老卡怎么回事
  • 做網(wǎng)站的屬于什么崗位網(wǎng)上推廣賺錢方法
  • wordpress 推薦環(huán)境關(guān)鍵詞seo排名優(yōu)化
  • 自適應(yīng)網(wǎng)站 seo怎么做濟(jì)南網(wǎng)站建設(shè)老威
  • 杭州網(wǎng)站建設(shè)咨詢藍(lán)韻網(wǎng)絡(luò)長(zhǎng)尾關(guān)鍵詞挖掘站長(zhǎng)工具
  • 中學(xué)生制作的網(wǎng)站網(wǎng)絡(luò)運(yùn)營(yíng)
  • 做網(wǎng)站需要基礎(chǔ)嗎互聯(lián)網(wǎng)營(yíng)銷師培訓(xùn)內(nèi)容
  • 品牌設(shè)計(jì)網(wǎng)站怎樣推廣自己的廣告
  • 網(wǎng)站策劃書最后一步怎么做采集站seo提高收錄
  • 寧夏銀川網(wǎng)站建設(shè)游戲app拉新平臺(tái)
  • 怎么做網(wǎng)站賺錢廣告營(yíng)銷案例分析
  • wordpress openbox主題山東服務(wù)好的seo
  • 做彩票網(wǎng)站要什么接口互聯(lián)網(wǎng)推廣與營(yíng)銷
  • 平面設(shè)計(jì)專用網(wǎng)站臨安網(wǎng)站seo
  • 內(nèi)力網(wǎng)站建設(shè)公司宣傳軟文
  • 做網(wǎng)站頁面的軟件海淀區(qū)seo搜索引擎
  • 網(wǎng)站建設(shè)常用英語網(wǎng)店運(yùn)營(yíng)
  • 中山做外貿(mào)網(wǎng)站建設(shè)百度小說排行榜完本
  • 做誘惑類cpa網(wǎng)站經(jīng)驗(yàn)百度賬號(hào)注冊(cè)平臺(tái)
  • xp做的網(wǎng)站有連接限制seo優(yōu)化網(wǎng)站技術(shù)排名百度推廣
  • 沒有注冊(cè)公司怎么做網(wǎng)站性價(jià)比高seo排名
  • 無錫公司網(wǎng)站建設(shè)電話百度做網(wǎng)站需要多少錢
  • 濰坊市網(wǎng)站建設(shè)公司西部數(shù)碼域名注冊(cè)官網(wǎng)
  • 網(wǎng)站優(yōu)化推廣怎么做電商營(yíng)銷策劃方案
  • 做公司網(wǎng)站需要有座機(jī)嗎微信crm客戶管理系統(tǒng)
  • 企業(yè)網(wǎng)站建設(shè)顧問百度推廣后臺(tái)登陸官網(wǎng)
  • 網(wǎng)站用什么語言開發(fā)百度搜索怎么優(yōu)化
  • 淮南北京網(wǎng)站建設(shè)新網(wǎng)站如何推廣
  • wap網(wǎng)站為什么沒有了沈陽網(wǎng)絡(luò)seo公司