1. 折半
1.1 從一維數(shù)組中求一個(gè)值/下標(biāo)
724.尋找數(shù)組的中心索引 Find Pivot Index medium
將(總數(shù))減去(左邊上一次累加的和)減去(本次的值) = O(N)吮旅，（如果有2個(gè)中心值征候，只保留左邊的中間值）累加值可以對(duì)比前一次的寞酿，也可以對(duì)比當(dāng)前的
747.最大值至少是其他值的兩倍 Largest Number At Least Twice of easy
先求最大值下標(biāo)匠襟，再遍歷同事略過(guò)最大值下標(biāo)O(N)钝侠，可以考慮用s++,e--改成O(N/2)
1.2 根據(jù)一維數(shù)組，處理后返回一維數(shù)組
66. 數(shù)值加一 Plus One easy
法1. 使用隊(duì)列記錄酸舍，并用一個(gè)進(jìn)制位輔助表示是否+1(性能不好)
法2. 可以根據(jù)每個(gè)數(shù)是否為9帅韧，如果有一個(gè)不為9，都不會(huì)導(dǎo)致左位進(jìn)1啃勉，如果全都是9忽舟，則數(shù)組長(zhǎng)度+1，第一個(gè)值為1，其余值為0. time: O(n), space: O(1)
1.3 根據(jù)二維數(shù)組叮阅，找規(guī)律刁品，處理后返回一維數(shù)組
498. 對(duì)角線遍歷矩陣 Diagonal Traverse medium
難點(diǎn)在找規(guī)律，用row和col表示下標(biāo)浩姥，返回的總數(shù)是mn個(gè)數(shù)組哑诊，方向就2個(gè){上右{-1, 1}，左下{1, -1}}表示及刻，并且出界情況就4種镀裤，row<0 || col<0 || row >m-1 || col >n-1，在不同的情況*下改變對(duì)應(yīng)的row和col下標(biāo) 以及 方向d{0, 1}
54. Spiral Matrix 螺旋矩陣 medium
找規(guī)律缴饭，用row和col表示下標(biāo)暑劝，返回的總數(shù)是mn個(gè)數(shù)組，并且邊界值[上下左右]颗搂，每次改變方向時(shí)要減少對(duì)應(yīng)的邊界值-1担猛，在不同的情況*下改變對(duì)應(yīng)的row和col下標(biāo)，方向4個(gè)丢氢，{右{0,1}傅联，下{1,0}，左{0,-1}疚察，上{-1,0}}蒸走，
1.4 查詢數(shù)據(jù)在有序列表中位置 若不存在則預(yù)估位置
35. 查詢一維數(shù)組插入的位置 Search Insert Position easy
折半法要注意
(a + b) /2容易越界，可以用[a + (a-b)/2]
時(shí)間復(fù)雜度O(logn)貌嫡，空間復(fù)雜度O(1)
折半法
取最后定位的下標(biāo)low
74. 查詢二維有序數(shù)組中某個(gè)值下標(biāo) search-a-2d-matrix easy
時(shí)間復(fù)雜度O(logn)比驻，空間復(fù)雜度O(1)
折半法
雖然是二維數(shù)組，但是由于是有序的
240. 查詢二維無(wú)序數(shù)組中某個(gè)值下標(biāo) Search a 2D Matrix II medium
時(shí)間復(fù)雜度O(m+n)岛抄，空間復(fù)雜度O(1)
找規(guī)律
找到第1列的最右值
如果值比目標(biāo)大别惦，則向下移動(dòng)行
如果值比目標(biāo)小，則向左移動(dòng)列
153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值(數(shù)據(jù)不重復(fù)) Find Minimum in Rotated Sorted Array medium
法1. dp方法 + 折半 同時(shí)運(yùn)用了規(guī)則夫椭，有序時(shí)最小值一定是頭一個(gè)掸掸，無(wú)序時(shí)遍歷
時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(1)
設(shè)置一個(gè)min=Integer.MAX_VALUE蹭秋，每次傳入對(duì)應(yīng)的start和end扰付，如果nums[start]<nums[end]說(shuō)明nums[start]是最小的做比對(duì)直接返回，否則設(shè)下的一定是無(wú)序的感凤，折半悯周，if(nums[start]<=nums[mid])說(shuō)明最小值在另一邊
法2. 折半
時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(1)
如果nums[mid]>nums[mid+1]則mid+1最小值陪竿，如果nums[mid-1]>nums[mid]則mid最小值禽翼，否則nums[mid]>nums[0]意味最小值在右邊
法3. 折半
時(shí)間復(fù)雜度O(logn)屠橄，空間復(fù)雜度O(1)
先定位到最小值所在下標(biāo)，nums[mid]>nums[hi]闰挡，意味著最小值在右側(cè)->lo=mid+1; 否則在左側(cè)->hi=mid;
33. 尋找旋轉(zhuǎn)排序數(shù)組中值的下標(biāo)(數(shù)據(jù)不重復(fù)) Search in Rotated Sorted Array medium
時(shí)間復(fù)雜度O(logn)锐墙，空間復(fù)雜度O(1)
先定位到最小值所在下標(biāo)，由于數(shù)組是有序的长酗，那下標(biāo)則為偏移量溪北，使用折半查找，每次中位數(shù)+偏移值
81. 搜索旋轉(zhuǎn)排序數(shù)組(數(shù)據(jù)重復(fù)) II Search in Rotated Sorted Array II
todo
1.5 括號(hào)問(wèn)題
20. 有效的括號(hào) valid parentheses easy
使用stack校驗(yàn)
22. 輸入括號(hào)夺脾，輸出所有有效配對(duì)生成 Generate Parentheses medium
法1. 回溯法 時(shí)間復(fù)雜度O(),空間復(fù)雜度O(n)
使用開(kāi)關(guān)括號(hào)的特性之拨，進(jìn)行回溯，記錄一個(gè)值用s.length()==n做條件
1.6 快速逼近目標(biāo)值
744. 尋找比目標(biāo)字母大的最小字母 Find Smallest Letter Greater Than Target easy
法1. 時(shí)間復(fù)雜度O(logn) 空間復(fù)雜度O(1)
折半法咧叭，定位到i為目標(biāo)值下標(biāo)蚀乔，判斷i是否為最后一個(gè)值，是取第一個(gè)值
374. 猜數(shù)字大小 Guess Number Higher or Lower easy
法1. 時(shí)間復(fù)雜度O(logn) 空間復(fù)雜度O(1)
折半法菲茬，每次取中間值對(duì)比大小
375. 猜數(shù)字大小II Guess Number Higher or Lower II medium
todo
2. 字符串
2.1 傳入字符串吉挣，處理邏輯，返回字符串
67. Add Binary 二進(jìn)制求和 easy
從尾數(shù)開(kāi)始婉弹，以長(zhǎng)字符串做條件睬魂，從尾往頭遍歷，總和有3镀赌，2氯哮，1，0類型佩脊，設(shè)置一個(gè)全局增量
890. 查找和替換模式 Find and Replace Pattern
法1. 時(shí)間復(fù)雜度O(mn)蛙粘，空間復(fù)雜度O(mn) ，m是字符串?dāng)?shù)組個(gè)數(shù)威彰，n是字符串長(zhǎng)度
使用兩個(gè)Map，一個(gè)保存key=匹配模式,value=值穴肘，一個(gè)key=目標(biāo)值,value=匹配模式歇盼，逐個(gè)對(duì)比
3. 字符串/數(shù)組/雙指針
3.1 承載水位問(wèn)題
11. 容器可承載最大水位 Container With Most Water medium
法1. 雙指針，時(shí)間復(fù)雜度O(n)评抚，空間復(fù)雜度O(1)
寬度總是減少的
每次將水位低的一邊縮容豹缀，因?yàn)榈偷囊环經(jīng)Q定了上限
