1、二分查找
二分查找思想簡單，但是在實(shí)現(xiàn)時(shí)有一些需要注意的細(xì)節(jié)：
1、在計(jì)算 mid 時(shí)不能使用 mid = (l + h) / 2 這種方式，因?yàn)?l + h 可能會(huì)導(dǎo)致加法溢出，應(yīng)該使用 mid = l + (h - l) / 2。
2、對(duì) h 的賦值和循環(huán)條件有關(guān)，當(dāng)循環(huán)條件為 l <= h 時(shí)，h = mid - 1；當(dāng)循環(huán)條件為 l < h 時(shí)，h = mid。解釋如下：在循環(huán)條件為 l <= h 時(shí)，如果 h = mid，會(huì)出現(xiàn)循環(huán)無法退出的情況，例如 l = 1，h = 1，此時(shí) mid 也等于 1，如果此時(shí)繼續(xù)執(zhí)行 h = mid，那么就會(huì)無限循環(huán)；在循環(huán)條件為 l < h，如果 h = mid - 1，會(huì)錯(cuò)誤跳過查找的數(shù)，例如對(duì)于數(shù)組 [1,2,3]，要查找 1，最開始 l = 0，h = 2，mid = 1，判斷 key < arr[mid] 執(zhí)行 h = mid - 1 = 0，此時(shí)循環(huán)退出，直接把查找的數(shù)跳過了。
3、l 的賦值一般都為 l = mid + 1。
public int search(int key, int[] arr) {
? ? int l=0, h=arr.length-1;
????while(l<=h) {
????????int mid=l+(h-l)/2;
????????if(key==arr[mid]) return mid;
????????if(key<arr[mid]) h=mid-1;
????????else l=mid+1;? ??
????}
????return-1;
}
求開方
一個(gè)數(shù) x 的開方 sqrt 一定在 0 ~ x 之間，并且滿足 sqrt == x / sqrt ?？梢岳枚植檎以?0 ~ x 之間查找 sqrt。
擺硬幣
題目描述：第 i 行擺 i 個(gè)，統(tǒng)計(jì)能夠擺的行數(shù)。
返回 h 而不是 l，因?yàn)閿[的硬幣最后一行不能算進(jìn)去。
有序數(shù)組的 Single Element
題目描述：一個(gè)有序數(shù)組只有一個(gè)數(shù)不出現(xiàn)兩次，找出這個(gè)數(shù)。
2、貪心思想
貪心思想保證每次操作都是局部最優(yōu)的，并且最后得到的結(jié)果是全局最優(yōu)的。
分配餅干
Leetcode : 455. Assign Cookies (Easy)
題目描述：每個(gè)孩子都有一個(gè)滿足度，每個(gè)餅干都有一個(gè)大小，只有餅干的大小大于一個(gè)孩子的滿足度，該孩子才會(huì)獲得滿足。求解最多可以獲得滿足的孩子數(shù)量。
因?yàn)樽钚〉暮⒆幼钊菀椎玫綕M足，因此先滿足最小孩子。給一個(gè)孩子的餅干應(yīng)當(dāng)盡量小又能滿足該孩子，這樣大餅干就能拿來給滿足度比較大的孩子。
證明：假設(shè)在某次選擇中，貪心策略選擇給第 i 個(gè)孩子分配第 m 個(gè)餅干，并且第 i 個(gè)孩子滿足度最小，第 m 個(gè)餅干為可以滿足第 i 個(gè)孩子的最小餅干，利用貪心策略最終可以滿足 k 個(gè)孩子。假設(shè)最優(yōu)策略在這次選擇中給 i 個(gè)孩子分配第 n 個(gè)餅干，并且這個(gè)餅干大于第 m 個(gè)餅干。我們發(fā)現(xiàn)使用第 m 個(gè)餅干去替代第 n 個(gè)餅干完全不影響后續(xù)的結(jié)果，因此不存在比貪心策略更優(yōu)的策略，即貪心策略就是最優(yōu)策略。
判斷是否為子串
分隔字符串使同種字符出現(xiàn)在一起
3、雙指針
雙指針主要用于遍歷數(shù)組，兩個(gè)指針指向不同的元素，從而協(xié)同完成任務(wù)。
從一個(gè)已經(jīng)排序的數(shù)組中查找出兩個(gè)數(shù)，使它們的和為 0
使用雙指針，一個(gè)指針指向元素較小的值，一個(gè)指針指向元素較大的值。指向較小元素的指針從頭向尾遍歷，指向較大元素的指針從尾向頭遍歷。
如果兩個(gè)指針指向元素的和 sum == target，那么得到要求的結(jié)果；如果 sum > target，移動(dòng)較大的元素，使 sum 變小一些；如果 sum < target，移動(dòng)較小的元素，使 sum 變大一些。
4、排序
快速選擇
一般用于求解?Kth Element?問題，可以在 O(n) 時(shí)間復(fù)雜度，O(1) 空間復(fù)雜度完成求解工作。
與快速排序一樣，快速選擇一般需要先打亂數(shù)組，否則最壞情況下時(shí)間復(fù)雜度為 O(n2)。
堆排序
堆排序用于求解?TopK Elements?問題，通過維護(hù)一個(gè)大小為 K 的堆，堆中的元素就是 TopK Elements。當(dāng)然它也可以用于求解 Kth Element 問題，因?yàn)樽詈蟪龆训哪莻€(gè)元素就是 Kth Element?？焖龠x擇也可以求解 TopK Elements 問題，因?yàn)檎业?Kth Element 之后，再遍歷一次數(shù)組，所有小于等于 Kth Element 的元素都是 TopK Elements?？梢钥吹?，快速選擇和堆排序都可以求解 Kth Element 和 TopK Elements 問題。
桶排序
找出出現(xiàn)頻率最多的 k 個(gè)數(shù)（頻率為0的，頻率為1的，...）
5、搜索
（1）BFS
廣度優(yōu)先搜索的搜索過程有點(diǎn)像一層一層地進(jìn)行遍歷：從節(jié)點(diǎn) 0 出發(fā)，遍歷到 6、2、1 和 5 這四個(gè)新節(jié)點(diǎn)。
繼續(xù)從 6 開始遍歷，得到節(jié)點(diǎn) 4 ；從 2 開始遍歷，沒有下一個(gè)節(jié)點(diǎn)；從 1 開始遍歷，沒有下一個(gè)節(jié)點(diǎn)；從 5 開始遍歷，得到 3 和 4 節(jié)點(diǎn)。這一輪總共得到兩個(gè)新節(jié)點(diǎn)：4 和 3 。
反復(fù)從新節(jié)點(diǎn)出發(fā)進(jìn)行上述的遍歷操作。
可以看到，每一輪遍歷的節(jié)點(diǎn)都與根節(jié)點(diǎn)路徑長度相同。設(shè) di?表示第 i 個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)的路徑長度，推導(dǎo)出一個(gè)結(jié)論：對(duì)于先遍歷的節(jié)點(diǎn) i 與后遍歷的節(jié)點(diǎn) j，有 di<=dj。利用這個(gè)結(jié)論，可以求解最短路徑?最優(yōu)解?問題：第一次遍歷到目的節(jié)點(diǎn)，其所經(jīng)過的路徑為最短路徑，如果繼續(xù)遍歷，之后再遍歷到目的節(jié)點(diǎn)，所經(jīng)過的路徑就不是最短路徑。
在程序?qū)崿F(xiàn) BFS 時(shí)需要考慮以下問題：
隊(duì)列：用來存儲(chǔ)每一輪遍歷的節(jié)點(diǎn)
標(biāo)記：對(duì)于遍歷過得節(jié)點(diǎn)，應(yīng)該將它標(biāo)記，防止重復(fù)遍歷；
計(jì)算在網(wǎng)格中從原點(diǎn)到特定點(diǎn)的最短路徑長度
[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]
（2）DFS
廣度優(yōu)先搜索一層一層遍歷，每一層遍歷到的所有新節(jié)點(diǎn)，要用隊(duì)列先存儲(chǔ)起來以備下一層遍歷的時(shí)候再遍歷；而深度優(yōu)先搜索在遍歷到一個(gè)新節(jié)點(diǎn)時(shí)立馬對(duì)新節(jié)點(diǎn)進(jìn)行遍歷：從節(jié)點(diǎn) 0 出發(fā)開始遍歷，得到到新節(jié)點(diǎn) 6 時(shí)，立馬對(duì)新節(jié)點(diǎn) 6 進(jìn)行遍歷，得到新節(jié)點(diǎn) 4；如此反復(fù)以這種方式遍歷新節(jié)點(diǎn)，直到?jīng)]有新節(jié)點(diǎn)了，此時(shí)返回。返回到根節(jié)點(diǎn) 0 的情況是，繼續(xù)對(duì)根節(jié)點(diǎn) 0 進(jìn)行遍歷，得到新節(jié)點(diǎn) 2，然后繼續(xù)以上步驟。
從一個(gè)節(jié)點(diǎn)出發(fā)，使用 DFS 對(duì)一個(gè)圖進(jìn)行遍歷時(shí)，能夠遍歷到的節(jié)點(diǎn)都是從初始節(jié)點(diǎn)可達(dá)的，DFS 常用來求解這種?可達(dá)性?問題。
在程序?qū)崿F(xiàn) DFS 時(shí)需要考慮以下問題：
棧：用棧來保存當(dāng)前節(jié)點(diǎn)信息，當(dāng)遍歷新節(jié)點(diǎn)返回時(shí)能夠繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)。也可以使用遞歸棧。
標(biāo)記：和 BFS 一樣同樣需要對(duì)已經(jīng)遍歷過的節(jié)點(diǎn)進(jìn)行標(biāo)記。
查找最大的連通面積
輸出二叉樹中所有從根到葉子的路徑
（3）回溯
回溯是 DFS 的一種，它不是用在遍歷圖的節(jié)點(diǎn)上，而是用于求解?排列組合?問題，例如有 { 'a','b','c' } 三個(gè)字符，求解所有由這三個(gè)字符排列得到的字符串。
在程序?qū)崿F(xiàn)時(shí)，回溯需要注意對(duì)元素進(jìn)行標(biāo)記的問題。使用遞歸實(shí)現(xiàn)的回溯，在訪問一個(gè)新元素進(jìn)入新的遞歸調(diào)用，此時(shí)需要將新元素標(biāo)記為已經(jīng)訪問，這樣才能在繼續(xù)遞歸調(diào)用時(shí)不用重復(fù)訪問該元素；但是在遞歸返回時(shí)，需要將該元素標(biāo)記為未訪問，因?yàn)橹恍枰ＷC在一個(gè)遞歸鏈中不同時(shí)訪問一個(gè)元素，而在不同的遞歸鏈?zhǔn)强梢栽L問已經(jīng)訪問過但是不在當(dāng)前遞歸鏈中的元素。
在矩陣中尋找字符串
IP地址劃分
6、分治
動(dòng)態(tài)規(guī)劃
遞歸和動(dòng)態(tài)規(guī)劃都是將原問題拆成多個(gè)子問題然后求解，他們之間最本質(zhì)的區(qū)別是，動(dòng)態(tài)規(guī)劃保存了子問題的解。
（1）分割整數(shù)
分割整數(shù)構(gòu)成字母字符串
（2）矩陣路徑
（3）斐波那契數(shù)列
爬樓梯
（4）最長遞增子序列、最長公共子序列
（5）0-1背包(無法使用貪心算法)
有一個(gè)容量為 N 的背包，要用這個(gè)背包裝下物品的價(jià)值最大，這些物品有兩個(gè)屬性：體積 w 和價(jià)值 v。
定義一個(gè)二維數(shù)組 dp 存儲(chǔ)最大價(jià)值，其中 dp[i][j] 表示體積不超過 j 的情況下，前 i 件物品能達(dá)到的最大價(jià)值。設(shè)第 i 件物品體積為 w，價(jià)值為 v，根據(jù)第 i 件物品是否添加到背包中，可以分兩種情況討論：
① 第 i 件物品沒添加到背包，總體積不超過 j 的前 i 件物品的最大價(jià)值就是總體積不超過 j 的前 i-1 件物品的最大價(jià)值，dp[i][j] = dp[i-1][j]。
② 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取決于哪種情況下最大價(jià)值更大。
因此：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
空間優(yōu)化:在程序?qū)崿F(xiàn)時(shí)可以對(duì) 0-1 背包做優(yōu)化。觀察狀態(tài)轉(zhuǎn)移方程可以知道，前 i 件物品的狀態(tài)僅由前 i-1 件物品的狀態(tài)有關(guān)，因此可以將 dp 定義為一維數(shù)組，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此時(shí)，d[j] = max(dp[j], dp[j-w]+v)
劃分?jǐn)?shù)組為和相等的兩部分（注意從后往前動(dòng)態(tài)規(guī)劃）
找零錢
（6）數(shù)組區(qū)間
數(shù)學(xué)
（1）素?cái)?shù)
素?cái)?shù)分解
每一個(gè)數(shù)都可以分解成素?cái)?shù)的乘積
整除
令 x = 2^m0?* 3^m1?* 5^m2?* 7^m3?* 11^m4?* …令 y = 2^n0?* 3^n1?* 5^n2?* 7^n3?* 11^n4?* …
如果 x 整除 y（y mod x == 0），則對(duì)于所有 i，mi <= ni。
x 和 y 的?最大公約數(shù)?為：gcd(x,y) = 2^min(m0,n0)?* 3^min(m1,n1)?* 5^min(m2,n2)?* ...
x 和 y 的?最小公倍數(shù)?為：lcm(x,y) = 2^max(m0,n0)?* 3^max(m1,n1)?* 5^max(m2,n2)?* ...
（2）最大公約數(shù)
最小公倍數(shù)為兩數(shù)的乘積除以最大公約數(shù)。
對(duì)于 a 和 b 的最大公約數(shù) f(a, b)，有：
1. 如果 a 和 b 均為偶數(shù)，f(a, b) = 2*f(a/2, b/2);2. 如果 a 是偶數(shù) b 是奇數(shù)，f(a, b) = f(a/2, b);3. 如果 b 是偶數(shù) a 是奇數(shù)，f(a, b) = f(a, b/2);4. 如果 a 和 b 均為奇數(shù)，f(a, b) = f(a, a-b);
乘 2 和除 2 都可以轉(zhuǎn)換為移位操作。
（3）進(jìn)制轉(zhuǎn)換
（4）階乘
（5）字符串加法減法
二進(jìn)制加法
字符串加法
（6）相遇問題
移動(dòng)數(shù)組元素使所有的數(shù)組元素都相等
題目描述：每次可以對(duì)一個(gè)數(shù)組元素加一或者減一，求最小的改變次數(shù)。
這是個(gè)典型的相遇問題，移動(dòng)距離最小的方式是所有元素都移動(dòng)到中位數(shù)。理由如下：
設(shè) m 為中位數(shù)。a 和 b 是 m 兩邊的兩個(gè)元素，且 b > a。要使 a 和 b 相等，它們總共移動(dòng)的次數(shù)為 b - a，這個(gè)值等于 (b - m) + (m - a)，也就是把這兩個(gè)數(shù)移動(dòng)到中位數(shù)的移動(dòng)次數(shù)。
設(shè)數(shù)組長度為 N，則可以找到 N/2 對(duì) a 和 b 的組合，使它們都移動(dòng)到 m 的位置。
利用快速排序找到中位數(shù)：首先確立基準(zhǔn)值privot=nums[(l+r)/2]，然后分別從數(shù)組的左-右、右-左遍歷數(shù)組，分別找到比privot大/小的值nums[l]、nums[r]，交換這兩個(gè)值。到l>r時(shí)停止，接著分別對(duì)大于privot的右半部分和小于privot的左半部分做遞歸。
數(shù)據(jù)結(jié)構(gòu)相關(guān)
（1）棧和隊(duì)列
用棧實(shí)現(xiàn)隊(duì)列
用隊(duì)列實(shí)現(xiàn)棧
最小值棧(用兩個(gè)棧實(shí)現(xiàn)，一個(gè)存儲(chǔ)數(shù)據(jù)，一個(gè)存儲(chǔ)最小值)
（2）哈希表
利用 Hash Table 可以快速查找一個(gè)元素是否存在等問題，但是需要一定的空間來存儲(chǔ)。在優(yōu)先考慮時(shí)間復(fù)雜度的情況下，可以利用 Hash Table 這種空間換取時(shí)間的做法。
（3）字符串
兩個(gè)字符串包含的字符是否完全相同——記錄每個(gè)字符串出現(xiàn)的次數(shù)
判斷一個(gè)整數(shù)是否是回文數(shù)
字符串中單詞的翻轉(zhuǎn)
（4）數(shù)組與矩陣
（5）鏈表
判斷兩個(gè)鏈表的交點(diǎn)——從后往前訪問兩個(gè)鏈表
鏈表反轉(zhuǎn)——頭插法，獲取最后一個(gè)節(jié)點(diǎn)并賦值給new，temp為head，tmp為head->next，賦temp->next為new->next，new->next為temp。循環(huán)。
歸并兩個(gè)有序的鏈表——遞歸
（6）樹
遞歸
一棵樹要么是空樹，要么有兩個(gè)指針，每個(gè)指針指向一棵樹。樹是一種遞歸結(jié)構(gòu)，很多樹的問題可以使用遞歸來處理。
樹的高度 遞歸計(jì)算每個(gè)節(jié)點(diǎn)的高度（左右子樹高度取最大值+1）
翻轉(zhuǎn)樹——返回子節(jié)點(diǎn)的翻轉(zhuǎn)后的節(jié)點(diǎn)
歸并兩棵樹
最近公共祖先（二叉搜索樹、普通二叉樹）
層次遍歷
使用 BFS，不需要使用兩個(gè)隊(duì)列來分別存儲(chǔ)當(dāng)前層的節(jié)點(diǎn)和下一層的節(jié)點(diǎn)， 因?yàn)樵陂_始遍歷一層的節(jié)點(diǎn)時(shí)，當(dāng)前隊(duì)列中的節(jié)點(diǎn)數(shù)就是當(dāng)前層的節(jié)點(diǎn)數(shù)，只要控制遍歷這么多節(jié)點(diǎn)數(shù)，就能保證這次遍歷的都是當(dāng)前層的節(jié)點(diǎn)。
計(jì)算一棵樹每層節(jié)點(diǎn)的平均數(shù)
前中后序遍歷
① 前序
void dfs(TreeNoderoot){? ??
????visit(root);? ??
????dfs(root.left);? ??
????dfs(root.right);}
② 中序
void dfs(TreeNoderoot){?
?? dfs(root.left);
? ? visit(root);
? ? dfs(root.right);}
③ 后序
void dfs(TreeNoderoot){
? ? dfs(root.left);
? ? dfs(root.right);
? ? visit(root);}
BST（二叉搜索樹）
主要利用 BST 中序遍歷有序的特點(diǎn)。
在BST中尋找兩個(gè)節(jié)點(diǎn)，使它們的和成為一個(gè)給定值。
Trie（前綴樹、字典樹）用于判斷字符串是否存在或者是否具有某種字符串前綴
（7）圖的位運(yùn)算
1. 基本原理
0s 表示 一串 0 ，1s 表示一串 1。
x ^0s= x? ? ? x &0s=0x |0s= x
x ^1s= \~x? ? x &1s= x? ? ? x |1s=1s
x ^ x =0x & x = x? ? ? x | x = x
① 利用 x ^ 1s = ~x 的特點(diǎn)，可以將位級(jí)表示翻轉(zhuǎn)；利用 x ^ x = 0 的特點(diǎn)，可以將三個(gè)數(shù)中重復(fù)的兩個(gè)數(shù)去除，只留下另一個(gè)數(shù)；② 利用 x & 0s = 0 和 x & 1s = x 的特點(diǎn)，可以實(shí)現(xiàn)掩碼操作。一個(gè)數(shù) num 與 mask ：00111100 進(jìn)行位與操作，只保留 num 中與 mask 的 1 部分相對(duì)應(yīng)的位；③ 利用 x | 0s = x 和 x | 1s = 1s 的特點(diǎn)，可以實(shí)現(xiàn)設(shè)置操作。一個(gè)數(shù) num 與 mask：00111100 進(jìn)行位或操作，將 num 中與 mask 的 1 部分相對(duì)應(yīng)的位都設(shè)置為 1 。
>> n 為算術(shù)右移，相當(dāng)于除以 2n；>>> n 為無符號(hào)右移，左邊會(huì)補(bǔ)上 0。<< n 為算術(shù)左移，相當(dāng)于乘以 2n。
n&(n-1) 該位運(yùn)算是去除 n 的位級(jí)表示中最低的那一位。例如對(duì)于二進(jìn)制表示 10110100，減去 1 得到 10110011，這兩個(gè)數(shù)相與得到 10110000。
n-n&(~n+1) 概運(yùn)算是去除 n 的位級(jí)表示中最高的那一位。
n&(-n) 該運(yùn)算得到 n 的位級(jí)表示中最低的那一位。-n 得到 n 的反碼加 1，對(duì)于二進(jìn)制表示 10110100，-n 得到 01001100，相與得到 00000100
2. mask 計(jì)算
3. 位操作舉例
① 獲取第 i 位
num & 00010000 != 0
(num&(1<<i))!=0;
② 將第 i 位設(shè)置為 1
num | 00010000
num|(1<<i);
③ 將第 i 位清除為 0
num & 11101111
num&(\~(1<<i))
④ 將最高位到第 i 位清除為 0
num & 00001111
num&((1<<i)-1);
⑤ 將第 0 位到第 i 位清除為 0
num & 11110000
num&(\~((1<<(i+1))-1));
⑥ 將第 i 位設(shè)置為 0 或者 1
先將第 i 位清零，然后將 v 左移 i 位，執(zhí)行“位或”運(yùn)算。
(num&(1<<i))|(v<<i);
