1. Search in Array
給定一個(gè)n個(gè)元素有序的（升序）整型數(shù)組nums?和一個(gè)目標(biāo)值target?，寫一個(gè)函數(shù)搜索nums中的?target，如果目標(biāo)值存在返回下標(biāo)，否則返回?-1。
解：標(biāo)準(zhǔn)的二分查找，這里使用左閉右開。
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
解：插入位置的二分查找，這里使用左閉右開，當(dāng)目標(biāo)值不存在的時(shí)候，注意最后一輪的左右邊界。
給你一個(gè)字符數(shù)組?letters，該數(shù)組按非遞減順序排序，以及一個(gè)字符?target。letters里至少有兩個(gè)不同的字符。返回letters中大于?target?的最小的字符。如果不存在這樣的字符，則返回letters?的第一個(gè)字符。
解：其實(shí)就是插入位置的二分查找。
1351. 統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)
給你一個(gè)m?* n的矩陣grid，矩陣中的元素?zé)o論是按行還是按列，都以非嚴(yán)格遞減順序排列。?請(qǐng)你統(tǒng)計(jì)并返回grid中?負(fù)數(shù)?的數(shù)目。
解：這道題其實(shí)不算二分法。從下往上，從做往右。如果 grid[i][j] 碰到負(fù)數(shù)，那本行右邊都是負(fù)數(shù)。向上一行，如果grid[i][j]為正，j向右走，直到負(fù)數(shù)。
34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個(gè)目標(biāo)值?target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。如果數(shù)組中不存在目標(biāo)值?target，返回[-1, -1]。
解：第一個(gè)思路很簡(jiǎn)單。因?yàn)槭钦麛?shù)，那就目標(biāo)值加減0.5，然后找插入位置即可。另一個(gè)思路是老老實(shí)實(shí)找第一個(gè)和最后一個(gè)位置。
給你一個(gè)區(qū)間數(shù)組?intervals?，其中intervals[i] = [starti, endi]?，且每個(gè)starti?都?不同?。區(qū)間?i?的?右側(cè)區(qū)間?可以記作區(qū)間?j?，并滿足?startj>= endi?，且?startj?最小化?。注意?i?可能等于?j?。返回一個(gè)由每個(gè)區(qū)間?i?的?右側(cè)區(qū)間?在intervals?中對(duì)應(yīng)下標(biāo)組成的數(shù)組。如果某個(gè)區(qū)間?i?不存在對(duì)應(yīng)的?右側(cè)區(qū)間?，則下標(biāo)?i?處的值設(shè)為?-1?。
解：用一個(gè)元組列表start_index記錄每個(gè)區(qū)間的起點(diǎn)和index。排序。然后對(duì)每個(gè)區(qū)間，去尋找終點(diǎn)在start_index中的插入位置。
設(shè)計(jì)一個(gè)基于時(shí)間的鍵值數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)可以在不同時(shí)間戳存儲(chǔ)對(duì)應(yīng)同一個(gè)鍵的多個(gè)值，并針對(duì)特定時(shí)間戳檢索鍵對(duì)應(yīng)的值。
實(shí)現(xiàn)?TimeMap?類：
TimeMap()?初始化數(shù)據(jù)結(jié)構(gòu)對(duì)象
void set(String key, String value, int timestamp)?存儲(chǔ)給定時(shí)間戳timestamp時(shí)的鍵key和值value。
String get(String key, int timestamp)返回key對(duì)應(yīng)的值，該值的時(shí)間戳應(yīng)小于等于 timestamp。如果有多個(gè)這樣的值，它將返回最大時(shí)間戳的值。如果沒有值，則返回空字符串（""）。
解：字典的key在不同時(shí)間戳可以儲(chǔ)存多個(gè)值。那value就用列表。每個(gè)列表元素都是一個(gè)元組。放入(時(shí)間戳，值)。這樣就有了一個(gè)以時(shí)間戳排序的列表。get就用二分法尋找。
實(shí)現(xiàn)支持下列接口的「快照數(shù)組」-?SnapshotArray：
SnapshotArray(int length)- 初始化一個(gè)與指定長度相等的 類數(shù)組 的數(shù)據(jù)結(jié)構(gòu)。初始時(shí)，每個(gè)元素都等于?0。
void set(index, val)- 會(huì)將指定索引index處的元素設(shè)置為val。
int snap()- 獲取該數(shù)組的快照，并返回快照的編號(hào)snap_id（快照號(hào)是調(diào)用snap()的總次數(shù)減去1）。
int get(index, snap_id)- 根據(jù)指定的snap_id選擇快照，并返回該快照指定索引?index的值。
解：對(duì)每個(gè)索引 index 建立一個(gè)字典。里面的鍵值對(duì)為 快照編號(hào)：值。因此查找的時(shí)候，由索引定位到字典。字典的key是快照編號(hào)。排序后，可以二分查找。這里需要注意，因?yàn)槊看慰煺蘸?，我們并沒有在字典中更改key的值。因此，要找到目標(biāo)快照的前一個(gè)快照編號(hào)。這里用bisect_right（無相同值，返回插入位置，有相同值，返回相同值后一位），然后減1.?
2.?Rotated Array
整數(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。
解：旋轉(zhuǎn)數(shù)組都是先判斷左右兩邊哪邊是有序。再判斷目標(biāo)值是否在有序的半邊。如果是，就找有序半邊，否則就找無序半邊。
153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
已知一個(gè)長度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。注意，數(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ù)組中的?最小元素?。
解：旋轉(zhuǎn)數(shù)組。先用 left mid 判斷哪邊有序。如果left < mid 則左邊為有序半邊，最小值left先記錄上。然后改變邊界，left = mid + 1。那下次while循環(huán)就處理無序的右半邊。如果left > mid 則右邊為有序半邊，最小值 mid 先記錄上。然后改變邊界，right = mid。那下次while循環(huán)就處理無序的左半邊。
154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
已知一個(gè)長度為?n?的數(shù)組，預(yù)先按照升序排列，經(jīng)由?1?到?n?次?旋轉(zhuǎn)?后，得到輸入數(shù)組。給你一個(gè)可能存在?重復(fù)?元素值的數(shù)組?nums?，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請(qǐng)你找出并返回?cái)?shù)組中的?最小元素?。
解：這題與上一題的區(qū)別在于可能存在相同的元素。解決的辦法也很簡(jiǎn)單：如果mid == left且這兩個(gè)索引不同，那就left前進(jìn)一位好了，直到不等，或者兩者索引相同。
3. Standard Search
你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。假設(shè)你有?n?個(gè)版本?[1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。
解：找到第一個(gè)壞的。這里我們用左閉右開。如果mid是壞的，right = mid。有可能mid就是第一個(gè)壞的，那其左邊都是好的就會(huì)找不到壞的。這其實(shí)沒有關(guān)系，因?yàn)槲覀儠?huì)在找到邊界的時(shí)候停止，且left + 1.返回 left 即可。
給你一個(gè)滿足下述兩條屬性的?m x n?整數(shù)矩陣：每行中的整數(shù)從左到右按非嚴(yán)格遞增順序排列。每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。給你一個(gè)整數(shù)?target?，如果?target?在矩陣中，返回?true?；否則，返回?false?。
解：這個(gè)矩陣其實(shí)可以拉長了變成一個(gè)array。
4. Math
給你一個(gè)正整數(shù)?num?。如果?num?是一個(gè)完全平方數(shù)，則返回?true?，否則返回?false?。完全平方數(shù)?是一個(gè)可以寫成某個(gè)整數(shù)的平方的整數(shù)。換句話說，它可以寫成某個(gè)整數(shù)和自身的乘積。不能使用任何內(nèi)置的庫函數(shù)，如?sqrt?。
解：用二分法從1到num+1去試。
給你一個(gè)非負(fù)整數(shù)?x?，計(jì)算并返回x的?算術(shù)平方根?。由于返回類型是整數(shù)，結(jié)果只保留?整數(shù)部分?，小數(shù)部分將被?舍去 。注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符 。
解：這道題和上題類似，唯一需要注意的是，返回的是left-1
你總共有n?枚硬幣，并計(jì)劃將它們按階梯狀排列。對(duì)于一個(gè)由?k?行組成的階梯，其第?i?行必須正好有?i?枚硬幣。階梯的最后一行?可能?是不完整的。給你一個(gè)數(shù)字n?，計(jì)算并返回可形成?完整階梯行?的總行數(shù)。
解：能形成完整k行階梯的數(shù)字是(k+1)/2*k。輸入n，找的n能形成的臺(tái)階數(shù)。
給你一個(gè)?嚴(yán)格升序排列的正整數(shù)數(shù)組?arr和一個(gè)整數(shù)k。請(qǐng)你找到這個(gè)數(shù)組里第k個(gè)缺失的正整數(shù)。
解：如果沒有缺失，那 arr[i] = i + 1，如果剛好是缺失的第k個(gè)整數(shù)，那 arr[i] = i + 1 + k.
給你一個(gè)整數(shù)數(shù)組?citations?，其中?citations[i]?表示研究者的第?i?篇論文被引用的次數(shù)，citations?已經(jīng)按照升序排列?。計(jì)算并返回該研究者的 h?指數(shù)。h 指數(shù)的定義：h 代表“高引用次數(shù)”（high citations），一名科研人員的?h?指數(shù)是指他（她）的 （n?篇論文中）至少?有?h?篇論文分別被引用了至少?h?次。
解：只要 citations[i] >= i+1就可以當(dāng)做h的候選。
給你一個(gè)僅由整數(shù)組成的有序數(shù)組，其中每個(gè)元素都會(huì)出現(xiàn)兩次，唯有一個(gè)數(shù)只會(huì)出現(xiàn)一次。請(qǐng)你找出并返回只出現(xiàn)一次的那個(gè)數(shù)。
解：檢查 i 的左右，如果左右都滿足（靠邊或者不等），那 i 就是那個(gè)唯一數(shù)。如果mid是偶數(shù)，且與前一個(gè)數(shù)相等。那單次數(shù)應(yīng)該出現(xiàn)在右側(cè)；如果mid是奇數(shù)，且與前一個(gè)數(shù)不等，那單次數(shù)應(yīng)該出現(xiàn)在右側(cè)。
給定一個(gè)長度為n的整數(shù)?山脈?數(shù)組arr，其中的值遞增到一個(gè)峰值元素然后遞減。返回峰值元素的下標(biāo)。
解：判斷峰值：左右都小于峰值。
給定一個(gè)?排序好?的數(shù)組arr?，兩個(gè)整數(shù)?k?和?x?，從數(shù)組中找到最靠近?x（兩數(shù)之差最?。┑?k?個(gè)數(shù)。返回的結(jié)果必須要是按升序排好的。整數(shù)?a?比整數(shù)?b?更接近?x?需要滿足：|a - x| < |b - x|?或者 |a - x| == |b - x|?且?a < b。
解：目標(biāo)是找到區(qū)間的起始點(diǎn)。認(rèn)真看注釋。
給定兩個(gè)大小分別為?m?和?n?的正序（從小到大）數(shù)組nums1?和nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的?中位數(shù)?。算法的時(shí)間復(fù)雜度應(yīng)該為?O(log (m+n))?。
解： 在兩個(gè)數(shù)組內(nèi)各自找一個(gè)分割點(diǎn) X Y。Y = (len1 + len2 + 1) // 2 - X，以保證在兩個(gè)序列中，X Y 左邊的元素個(gè)數(shù)合起來有總數(shù)的一半。然后比較XY左右的元素，看是否滿足中位數(shù)的要求。
5. As A Tool
給定一個(gè)包含非負(fù)整數(shù)的數(shù)組nums?，返回其中可以組成三角形三條邊的三元組個(gè)數(shù)。
解：先留下正數(shù)，排序。然后用兩層循環(huán)枚舉前兩條較短的邊，接著用二分查找第三條邊。
給你兩個(gè)正整數(shù)數(shù)組spells?和potions，長度分別為n?和m，其中spells[i]表示第i個(gè)咒語的能量強(qiáng)度，potions[j]表示第j瓶藥水的能量強(qiáng)度。同時(shí)給你一個(gè)整數(shù)success。一個(gè)咒語和藥水的能量強(qiáng)度?相乘?如果大于等于success，那么它們視為一對(duì)成功的組合。請(qǐng)你返回一個(gè)長度為?n的整數(shù)數(shù)組?pairs，其中?pairs[i]是能跟第?i個(gè)咒語成功組合的?藥水數(shù)目。
解：把藥水排序，能成功的條件是藥水大于 success/spell
給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?target?。請(qǐng)你統(tǒng)計(jì)并返回?nums?中能滿足其最小元素與最大元素的?和?小于或等于?target?的?非空?子序列的數(shù)目。由于答案可能很大，請(qǐng)將結(jié)果對(duì)109+ 7取余后返回。
解：雙指針法：使用雙指針分別指向數(shù)組的兩端：左指針left指向數(shù)組的開始，右指針right指向數(shù)組的末尾。如果nums[left] + nums[right]小于等于target，則以nums[left]為最小值，且最大值不超過nums[right]的所有子序列都是合法的。在這種情況下，從left到right之間有2^(right - left)種合法子序列。
給你一個(gè)?下標(biāo)從 0 開始?的正整數(shù)數(shù)組w?，其中w[i]?代表第?i?個(gè)下標(biāo)的權(quán)重。請(qǐng)你實(shí)現(xiàn)一個(gè)函數(shù)pickIndex，它可以?隨機(jī)地?從范圍?[0, w.length - 1]?內(nèi)（含?0?和?w.length - 1）選出并返回一個(gè)下標(biāo)。選取下標(biāo)?i的?概率?為?w[i] / sum(w)?。例如，對(duì)于?w = [1, 3]，挑選下標(biāo)?0?的概率為?1 / (1 + 3)?= 0.25?（即，25%），而選取下標(biāo)?1?的概率為?3 / (1 + 3)?= 0.75（即，75%）。
解：先生成一個(gè)累加和，以 [1, 3] 為例子，累加和為 prefix_sum =?[1, 4]，prefix_sum[-1] = 4即為總和。
然后從[1, 4] 中隨機(jī)抽取一個(gè)正整數(shù)，隨機(jī)數(shù)落在[1,1] 和 [2,4]的概率分別是25%，75%。因此挑選下標(biāo)?0?的概率為25%，而選取下標(biāo)?1?的概率為75%。
給你一個(gè)整數(shù)數(shù)組?nums?，找到其中最長嚴(yán)格遞增子序列的長度。子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。
解：記住這個(gè)方法LIS！建立一個(gè)最長嚴(yán)格遞增單調(diào)棧。如果入棧的元素大于棧頂元素，直接入棧；否則，就用二分法尋找插入位置，替代插入位置的元素（由于用bisect_left返回的位置插入后，替代的是其身后較大的元素，因此也增加了遞增單調(diào)棧繼續(xù)增長的可能性）
給你一個(gè)二維整數(shù)數(shù)組?envelopes?，其中?envelopes[i] = [wi, hi]?，表示第?i?個(gè)信封的寬度和高度。當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。請(qǐng)計(jì)算?最多能有多少個(gè)?信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
解：應(yīng)用LIS方法。先給信封按照寬度從小到大排序。隨后高度按照從大到小排序（因?yàn)橄嗤瑢挾?，如果高度還從小到大排序，在應(yīng)用LIS方法的時(shí)候，相同寬度的信封可以套娃，應(yīng)避免）。之后對(duì)高度應(yīng)用LIS即可。
