1.前言

最近準(zhǔn)備開始刷算法題了，搜了很多相關(guān)的帖子，下面三個(gè)很不錯(cuò)，

計(jì)算機(jī)視覺秋招準(zhǔn)備過程看這個(gè)：??????計(jì)算機(jī)視覺算法工程師-秋招面經(jīng) - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/399813916

復(fù)習(xí)深度學(xué)習(xí)相關(guān)知識(shí)看深度學(xué)習(xí)500問：

深度學(xué)習(xí)500問(github.com)https://github.com/scutan90/DeepLearning-500-questions刷題看這個(gè)：

算法模板，最科學(xué)的刷題方式，最快速的刷題路徑，你值得擁有~ (github.com)https://github.com/greyireland/algorithm-pattern準(zhǔn)備每天學(xué)習(xí)一點(diǎn)，刷幾道題，后面將會(huì)持續(xù)更新。

2.基礎(chǔ)算法篇-二分搜索

2.1二分搜索模板

給一個(gè)有序數(shù)組和目標(biāo)值，找第一次/最后一次/任何一次出現(xiàn)的索引，如果沒有出現(xiàn)返回-1

模板四點(diǎn)要素

• 1、初始化：start=0、end=len-1

• 2、循環(huán)退出條件：start + 1 < end

• 3、比較中點(diǎn)和目標(biāo)值：A[mid] ==、 <、> target

• 4、判斷最后兩個(gè)元素是否符合：A[start]、A[end] ? target

時(shí)間復(fù)雜度 O(logn)，使用場景一般是有序數(shù)組的查找

模板： 模板分析：?二分查找 - LeetBook - 力扣（LeetCode）全球極客摯愛的技術(shù)成長平臺(tái)

如果是最簡單的二分搜索，不需要找第一個(gè)、最后一個(gè)位置、或者是沒有重復(fù)元素，可以使用模板#1，代碼更簡潔

其他情況用模板#3

2.2常見題目

（1）給定一個(gè)包含 n 個(gè)整數(shù)的排序數(shù)組，找出給定目標(biāo)值 target 的起始和結(jié)束位置。 如果目標(biāo)值不在數(shù)組中，則返回[-1, -1]

思路：核心點(diǎn)就是找第一個(gè) target 的索引，和最后一個(gè) target 的索引，所以用兩次二分搜索分別找第一次和最后一次的位置

func searchRange (A []int, target int) []int {if len(A) == 0 {return []int{-1, -1}}result := make([]int, 2)start := 0end := len(A) - 1for start+1 < end {mid := start + (end-start)/2if A[mid] > target {end = mid} else if A[mid] < target {start = mid} else {// 如果相等，應(yīng)該繼續(xù)向左找，就能找到第一個(gè)目標(biāo)值的位置end = mid}}// 搜索左邊的索引if A[start] == target {result[0] = start} else if A[end] == target {result[0] = end} else {result[0] = -1result[1] = -1return result}start = 0end = len(A) - 1for start+1 < end {mid := start + (end-start)/2if A[mid] > target {end = mid} else if A[mid] < target {start = mid} else {// 如果相等，應(yīng)該繼續(xù)向右找，就能找到最后一個(gè)目標(biāo)值的位置start = mid}}// 搜索右邊的索引if A[end] == target {result[1] = end} else if A[start] == target {result[1] = start} else {result[0] = -1result[1] = -1return result}return result
}

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

func searchInsert(nums []int, target int) int {// 思路：找到第一個(gè) >= target 的元素位置start := 0end := len(nums) - 1for start+1 < end {mid := start + (end-start)/2if nums[mid] == target {// 標(biāo)記開始位置start = mid} else if nums[mid] > target {end = mid} else {start = mid}}if nums[start] >= target {return start} else if nums[end] >= target {return end} else if nums[end] < target { // 目標(biāo)值比所有值都大return end + 1}return 0
}

（3）編寫一個(gè)高效的算法來判斷 m x n 矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：

• 每行中的整數(shù)從左到右按升序排列。

• 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

func searchMatrix(matrix [][]int, target int) bool {// 思路：將2緯數(shù)組轉(zhuǎn)為1維數(shù)組 進(jìn)行二分搜索if len(matrix) == 0 || len(matrix[0]) == 0 {return false}row := len(matrix)col := len(matrix[0])start := 0end := row*col - 1for start+1 < end {mid := start + (end-start)/2// 獲取2緯數(shù)組對應(yīng)值val := matrix[mid/col][mid%col]if val > target {end = mid} else if val < target {start = mid} else {return true}}if matrix[start/col][start%col] == target || matrix[end/col][end%col] == target{return true}return false
}

（4）假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。 你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號(hào) version 是否在單元測試中出錯(cuò)。實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對調(diào)用 API 的次數(shù)。

func firstBadVersion(n int) int {// 思路：二分搜索start := 0end := nfor start+1 < end {mid := start + (end - start)/2if isBadVersion(mid) {end = mid} else if isBadVersion(mid) == false {start = mid}}if isBadVersion(start) {return start}return end
}

?（5）假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。 請找出其中最小的元素。

func findMin(nums []int) int {// 思路：/ / 最后一個(gè)值作為target，然后往左移動(dòng)，最后比較start、end的值if len(nums) == 0 {return -1}start := 0end := len(nums) - 1for start+1 < end {mid := start + (end-start)/2// 最后一個(gè)元素值為targetif nums[mid] <= nums[end] {end = mid} else {start = mid}}if nums[start] > nums[end] {return nums[end]}return nums[start]
}

（6）假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn) ( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。 請找出其中最小的元素。(包含重復(fù)元素)?

func findMin(nums []int) int {// 思路：跳過重復(fù)元素，mid值和end值比較，分為兩種情況進(jìn)行處理if len(nums) == 0 {return -1}start := 0end := len(nums) - 1for start+1 < end {// 去除重復(fù)元素for start < end && nums[end] == nums[end-1] {end--}for start < end && nums[start] == nums[start+1] {start++}mid := start + (end-start)/2// 中間元素和最后一個(gè)元素比較（判斷中間點(diǎn)落在左邊上升區(qū)，還是右邊上升區(qū)）if nums[mid] <= nums[end] {end = mid} else {start = mid}}if nums[start] > nums[end] {return nums[end]}return nums[start]
}

（7）假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。 ( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。 搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。 你可以假設(shè)數(shù)組中不存在重復(fù)的元素。

func search(nums []int, target int) int {// 思路：/ / 兩條上升直線，四種情況判斷if len(nums) == 0 {return -1}start := 0end := len(nums) - 1for start+1 < end {mid := start + (end-start)/2// 相等直接返回if nums[mid] == target {return mid}// 判斷在那個(gè)區(qū)間，可能分為四種情況if nums[start] < nums[mid] {if nums[start] <= target && target <= nums[mid] {end = mid} else {start = mid}} else if nums[end] > nums[mid] {if nums[end] >= target && nums[mid] <= target {start = mid} else {end = mid}}}if nums[start] == target {return start} else if nums[end] == target {return end}return -1
}

（8）假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。 ( 例如，數(shù)組 [0,0,1,2,2,5,6] 可能變?yōu)?[2,5,6,0,0,1,2] )。 編寫一個(gè)函數(shù)來判斷給定的目標(biāo)值是否存在于數(shù)組中。若存在返回 true，否則返回 false。(包含重復(fù)元素)

func search(nums []int, target int) bool {// 思路：/ / 兩條上升直線，四種情況判斷，并且處理重復(fù)數(shù)字if len(nums) == 0 {return false}start := 0end := len(nums) - 1for start+1 < end {// 處理重復(fù)數(shù)字for start < end && nums[start] == nums[start+1] {start++}for start < end && nums[end] == nums[end-1] {end--}mid := start + (end-start)/2// 相等直接返回if nums[mid] == target {return true}// 判斷在那個(gè)區(qū)間，可能分為四種情況if nums[start] < nums[mid] {if nums[start] <= target && target <= nums[mid] {end = mid} else {start = mid}} else if nums[end] > nums[mid] {if nums[end] >= target && nums[mid] <= target {start = mid} else {end = mid}}}if nums[start] == target || nums[end] == target {return true}return false
}

3.leedcode實(shí)戰(zhàn)

3.1 第35題

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。請必須使用時(shí)間復(fù)雜度為?O(log n)?的算法。

class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""result = 0mid = 0start = 0end = len(nums) - 1while start + 1 < end:mid = start + (end - start)/2if nums[mid] == target:result = midreturn resultelif nums[mid] < target:start = midelif nums[mid] > target:end = midif nums[start] == target:result = startelif nums[end] == target:result = endelif nums[start] > target:result = startelif nums[start] < target and nums[end] > target:result = endelif nums[end] < target:result = end + 1return result

3.2第74題

給你一個(gè)滿足下述兩條屬性的?m x n?整數(shù)矩陣：

• 每行中的整數(shù)從左到右按非遞減順序排列。
• 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

給你一個(gè)整數(shù)?target?，如果?target?在矩陣中，返回?true?；否則，返回?false?。

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""row = len(matrix)col = len(matrix[0])start = 0end = row * col - 1result = Falsewhile start + 1 < end:mid = start + (end - start)/2if matrix[mid / col][mid % col] == target:result = Truereturn resultelif matrix[mid / col][mid % col] > target:end = midelif matrix[mid / col][mid % col] < target:start = midif matrix[start / col][start % col] == target or matrix[end / col][end % col] == target:result = Trueelse:result = Falsereturn result

?3.3第34題

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個(gè)目標(biāo)值?target。請你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。如果數(shù)組中不存在目標(biāo)值?target，返回?[-1, -1]。你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題。

心得：第一次沒寫出來，想的是先去除掉重復(fù)的部分。正確的做法應(yīng)該是在nums[mid]==target部分下文章，start=mid就是向后找結(jié)束位置，end=mid就是向前找起始位置。

class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""if len(nums) == 0:return [-1, -1]elif len(nums) == 1 :if nums[0] == target:return [0, 0]else:return [-1, -1]start = 0end = len(nums) - 1result = [-1, -1]while start + 1 < end:mid = start + (end - start)/2if nums[mid] > target:end = midelif nums[mid] < target:start = midelse:end = midif nums[start] == target:result[0] = startelif nums[end] == target:result[0] = endelse:result[0] = -1result[1] = -1return resultstart = 0end = len(nums) - 1while start + 1 < end:mid = start + (end - start)/2if nums[mid] > target:end = midelif nums[mid] < target:start = midelse:start = midif nums[end] == target:result[1] = endelif nums[start] == target:result[1] = startelse:result[0] = -1result[1] = -1return resultreturn result

3.4第33題

整數(shù)數(shù)組?nums?按升序排列，數(shù)組中的值?互不相同?。

在傳遞給函數(shù)之前，nums?在預(yù)先未知的某個(gè)下標(biāo)?k（0 <= k < nums.length）上進(jìn)行了?旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo)?從 0 開始?計(jì)數(shù)）。例如，?[0,1,2,4,5,6,7]?在下標(biāo)?3?處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2]?。

給你?旋轉(zhuǎn)后?的數(shù)組?nums?和一個(gè)整數(shù)?target?，如果?nums?中存在這個(gè)目標(biāo)值?target?，則返回它的下標(biāo)，否則返回?-1?。

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

心得：花了半小時(shí)沒做出來，一開始想著先用nums[mid]與target來做判斷，發(fā)現(xiàn)行不通，然后嘗試兩條上升的直線劃區(qū)域做，想法沒錯(cuò)但是陷入了誤區(qū)。正確方法是兩條上升的直線，然后利用start一定會(huì)移動(dòng)到mid和end一定會(huì)移動(dòng)到mid的條件來判斷。

定理一：只有在順序區(qū)間內(nèi)才可以通過區(qū)間兩端的數(shù)值判斷target是否在其中。

定理二：判斷順序區(qū)間還是亂序區(qū)間，只需要對比 left 和 right 是否是順序?qū)纯?#xff0c;left <= right，順序區(qū)間，否則亂序區(qū)間。

定理三：每次二分都會(huì)至少存在一個(gè)順序區(qū)間。（感謝@Gifted VVilburgiX補(bǔ)充）

通過不斷的用Mid二分，根據(jù)定理二，將整個(gè)數(shù)組劃分成順序區(qū)間和亂序區(qū)間，然后利用定理一判斷target是否在順序區(qū)間，如果在順序區(qū)間，下次循環(huán)就直接取順序區(qū)間，如果不在，那么下次循環(huán)就取亂序區(qū)間。

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""if len(nums) == 0:return -1start = 0end = len(nums) - 1result = 0while start + 1 < end:mid = start + (end - start)/2if nums[mid] == target:return midif nums[start] < nums[mid]:# 說明左半邊是有序的if target <= nums[mid] and target >= nums[start]:end = midelse:start = midelif nums[end] > nums[mid]:# 說明右半邊是有序的if target >= nums[mid] and target <= nums[end]:# 用來確定目標(biāo)是否在這一區(qū)域，決定保留哪邊。start = midelse:end = midif nums[start]==target:result = startelif nums[end]==target:result = endelse:result = -1return result

3.5第153題

已知一個(gè)長度為?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)。請你找出并返回?cái)?shù)組中的?最小元素?。

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

心得：第一次提交失敗，沒有考慮到順序數(shù)組的情況，所以加了一個(gè)if語句判斷是否是順序的。

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""if len(nums) == 1:return nums[0]start = 0end = len(nums) - 1while start + 1 < end:mid = start + (end - start)/2if nums[start] > nums[end]:if nums[start] < nums[mid]:start = midelif nums[mid] < nums[end]:end = midelse:return nums[0]if nums[start] > nums[end]:return nums[end]else:return nums[start]

?