動態(tài)規(guī)劃

111. 爬樓梯
思路
類似斐波那契數列
注意
考慮第 0 階的特殊情況

272. 爬樓梯 II
思路
類似上題厂财，只是從兩個變量變成了三個變量蹂季，注意特判下第 0齐帚、1庐冯、2 三階臺階

630. 騎士的最短路徑II
思路
騎士只能從左往右移動，所以從 (0, 0) 點出發(fā)沿著方向坐標先更新最左列數組慧妄，逐漸向右更新顷牌，直到 (n - 1, m - 1) 的位置
注意
對上一個點值和坐標是否越界的判斷注意書寫的正確

116. 跳躍游戲
思路
當前位置 i 是否可達由其前面的 0 到 i - 1 位置決定的，如果 j 位置可達且 j + A[j] >= i 則代表 i 可達塞淹，最后判斷 A.length - 1 位置是否可達

117. 跳躍游戲 II
思路
思路和上題相似窟蓝，但題目要求求出到達最小長度，所以將布爾數組換成整數數組饱普，Integer.MAX_VALUE 代表不可達运挫，其余數值代表從起始位置到當前位置的最小長度
錯誤
細節(jié)錯誤，忘記給 steps[0] 賦值 0

254. Drop Eggs
思路

哈希表與堆

128. 哈希函數
思路
背下來就好了
注意

1. 應將 ans 設為 long 類型套耕，否則當 key 很大時會溢出
2. 要記得取模

129. 重哈希
思路
新的 hash 表容量是原來2倍谁帕，遍歷原 hash 表，hash 表中元素模上 newSize 得到
newIndex冯袍，然后在 newIndex 對應位置的鏈表的結尾插入值
錯誤
while (hashTable[i] != null) 不能寫成 if (hashTable[i] == null) { continue; }
如果寫成 if 形式匈挖，當前 hash[i] 對應的位置如果是一個鏈表，那只會執(zhí)行第一個結點的rehash康愤，然后開始執(zhí)行 hash[i + 1]儡循，hash[i] 位置的鏈表第一個結點后面的所有結點都會被跳過

544. 前K大數
思路
用 PriorityQueue 實現(xiàn)一個大小為 k 的最小堆，堆中元素不足 k 不斷加入征冷，堆中元素等于 k 時把堆頂最小值拋出

606. 第K大的元素 II
思路
如果 N 和 K 在一個數量級上择膝，采用 quickSelect 來解題，如果 N >> K检激，采用 PriorityQueue 來解題
錯誤
最小堆要保持堆內元素個數在 k 個肴捉，這樣可以保證執(zhí)行 minHeap.peek() 時得到的是第 k 大的元素
所以有兩種寫法

for (int num : nums) {
     q.add(num);
     if (q.size() > k) {
         q.poll();
     }
}
return q.peek();

for (int num : nums) {
     if (q.size() == k) {
         q.poll();
     }
     q.add(num);
}
return q.peek();

先往堆內添加元素就大于 k 時再拋出這種寫法是對的，后往堆內添加元素就在等于 k 時就拋出這種寫法是錯的呵扛，因為最后一個拋出的元素可能比最后一個加入的元素更符合要求

612. K個最近的點
思路
定義最大堆每庆，元素一個接一個加入堆，堆中元素數量大于 k 時拋出
錯誤

1. Comparator 不會寫
2. 往堆里添加元素寫成了等于 k 時拋出今穿，然后加入元素這種形式
3. 未考慮堆中元素數目不足 k 的情況，即在往 results 中添加元素時伦籍，循環(huán)的結束條件應是 while (!heap.isEmpty()) 蓝晒，如果用 for (int i = 0; i < k; i++) 當元素數目不足 k 個時會出現(xiàn)空指針越界錯誤

545. 前K大數 II
思路
數據是動態(tài)的，用 PriorityQueue 來做
錯誤

1. 構造方法只是用來初始化賦值的帖鸦，構造方法中的變量芝薇，其他方法仍舊不能讀取
2. 迭代器寫的不熟，應該寫 while (it.hasNext()) 而不是 if (it.hasNext())

613. 優(yōu)秀成績
思路
分數可能重復作儿，但 id 不會重復洛二，每個學生有多個分數，以 id 為鍵，學生所有的分數構成的 PriorityQueue 為值組成 HashMap晾嘶，每個學生 id 對應一個 PriorityQueue
錯誤
Map.Entry使用不熟練

575. 表達式展開
思路

1. 用遞歸妓雾，對于當前層遞歸首先分四部分考慮左括號、右括號垒迂、數字械姻、以及其他，遞歸的好處是可以體現(xiàn)由大化小的能力机断，壞處是當嵌套太深時會棧溢出
   然后每一部分又要分別考慮此部分是在方括號內還是方括號外楷拳，括號內的話僅僅加入字符串記錄下來即可，將字符串傳入下一層遞歸處理吏奸，括號外則需要進行處理
   錯誤
   右括號處理完后要使 number = 0; subString = "";
2. 用棧
   從最左邊的右括號開始展開
   錯誤
   a. stack中的元素類型應為 Object 類型欢揖，如果設為 String 類型在執(zhí)行Integer count = (Integer) stack.pop();會出現(xiàn) String 無法轉化為 Integer 的錯誤
   b. 先有 stack.push(Integer.valueOf(number)); 然后執(zhí)行 Integer count = (Integer) stack.pop(); 才不會報錯；先將 number 轉化為 Integer 類型

兩根指針

607. 兩數之和-數據結構設計
思路
需要考慮到 3 + 3 = 6 時兩個 3 到底是不是同一個數
注意

1. map 和 list 的初值用構造器賦值
2. list 中每個元素只添加一次

587. 兩數之和 - 不同組成
思路
先排序奋蔚，兩根相向型指針浸颓，注意去重，num[left] + nums[right] < target 時
left++旺拉，nums[left] + nums[right] > target 時 right--

533. 兩數和的最接近值
思路
先排序产上，兩根相向型指針，不用考慮去重蛾狗，num[left] + nums[right] < target 時 left++晋涣，nums[left] + nums[right] > target 時 right--，同時要注意 differ 的更新

443. 兩數之和 II
思路
當找到第一個和大于 target 的 left 和 right 后沉桌，所有 left 到 right 之間的數全部都符合條件

610. 兩數和 - 差等于目標值
思路
需要新建 Pair 類(index 和 num)谢鹊，按照 num 大小排序后還能得到原來的下標，找到滿足調條件的兩個數留凭，同時注意 index 的大小關系
錯誤
細節(jié)錯誤還是很多

1. target 為負數沒注意
2. 對 j 的越界判斷
3. Comparator 的書寫

521.去除重復元素
思路

1. 先對數組排序佃扼，用兩根指針，len 指向當前最后一個不重復的數蔼夜，i 遍歷整個數組
2. 用 HashSet 去重兼耀，用 for (int num : arrays) 遍歷 Set 集合 arrays

604. 滑動窗口內數的和
思路
添一個刪一個維持當前 sum[i] 為 k 個元素之和

625. 數組劃分II
思路

1. 快速切分兩次，每次兩根指針
2. 快速切分一次求冷，每次三根指針

bugfree

鏈表與數組

599. 向循環(huán)有序鏈表插入節(jié)點
思路
考慮四種情況：

1. 鏈表為空
2. 鏈表只有一個結點
3. 鏈表有多個結點瘤运，但結點值全部相同
4. 鏈表有多個結點，結點值不同
   錯誤
   鏈表有多個值不同的結點時要考慮到比如往 30->50->2->2->3->5->7->9->11->20 總插入結點 2 這種在部分值相等結點中插入同樣值的結點
   prev.val < current.val && prev.val <= x && current.val >= x 判斷條件要加上等于

165. 合并兩個排序鏈表
思路
當模板背下來
注意
&& 別寫成 ||

102. 帶環(huán)鏈表
思路

1. 笨方法用 hash 表匠题，遍歷鏈表將表內未出現(xiàn)的元素加入表中拯坟，如果當前元素在表內出現(xiàn)過說明有環(huán)
2. 快慢指針，慢的一步韭山，快的兩步

bugfree

98. 鏈表排序
思路

1. 歸并排序
   先找中點郁季，按中點位置分成左右兩部分冷溃，分別排序，然后合并
   錯誤
   findMedian的判斷條件寫錯是while (fast.next != null && fast.next.next ! = null)不是while(slow != null && fast != null)快指針跑到終點梦裂，慢指針跑到一半距離
   注意
   先sortList(median.next)似枕，然后median.next = null，最后sortList(head)

2. 快速排序
   a. 先找中點塞琼，按中點值大小切分成小于菠净、等于、大于三部分彪杉，分別排序連接到一起
   錯誤
   總是忘記寫head = head.next
if (head == null || head.next == null) { return head; }如果寫return null在 head 只有一個結點時會報錯

35. 翻轉鏈表
思路
兩根指針 prev 和 head毅往，一前一后逐漸一個一個的改變指向，head 為空時派近，prev 正好指向原鏈表最后一個結點攀唯，即為翻轉后鏈表頭結點
錯誤
不要用 dummyNode 結點，用了等于給原鏈表增加了一個新的結點

450.K組翻轉鏈表
思路
定義 reverseK 函數實現(xiàn)每 k 個結點翻轉一次渴丸，外層調用while (curr != null) { curr = reverseK(curr, k); } 來實現(xiàn)整個鏈表的 k 組翻轉侯嘀；每 k 個結點翻轉的實現(xiàn)實際上就是在鏈表翻轉的基礎上修改代碼，先 for 循環(huán) k 次找到第 k 個結點谱轨， 需要判斷結點是否為空戒幔，nkPlus = nk.next，用 prev 和 current 兩根指針不斷翻轉鏈表土童，直到 current 指向 nkPlus 為止
錯誤
reverseK 中鏈表翻轉的判斷條件寫錯诗茎，是while (current != nkPlus)

5. 第k大元素
思路
quickSelect 模板
錯誤

1. 當 left == right 執(zhí)行 swap 操作時，要記得 left++ 和 right--
2. 每一輪切分完献汗，執(zhí)行遞歸的判斷條件記不清楚

if (start + k - 1 <= right) {
    return quickSelect(nums, start, right, k);
} else if (start + k - 1 >= left) {
    return quickSelect(nums, left, end, k - (left - start));
} else {
    return pivot;         // 也可以寫成 return nums[right + 1]
}

486. 合并k個排序數組
思路
將各行的第一個元素加入 PriorityQueue 構成的最小堆敢订，將拋出元素的值加入 results，然后將該元素所在行的下一元素加入最小堆
錯誤

1. Comparator 寫的不夠熟
2. 要對每一行進行越界和是否為空集判斷
3. int index = 0; 定義時要定義在 while 外面罢吃，否則一直都是在對 results[0] 反復賦值

471. 最高頻的K個單詞
思路
統(tǒng)計單詞出現(xiàn)次數楚午，定義一個按詞頻(詞頻相同時按詞典序排列)的堆，堆中元素不足 k 個時一直加入尿招，達到 k 個時要和堆頂元素比較矾柜，將更符合條件的元素留在堆頂
錯誤
在往堆內添加單詞時忘記去重，每個單詞應該只加入一次泊业，這時如果用 for (int i = 0; i < words.length; i++) 就會輸出多個一樣的單詞把沼，應該用代碼 for (String word : hash.keySet())

494. 雙隊列實現(xiàn)棧
思路
將 queue1 中元素除最后一個全部加入 queue2，吁伺，，
返回最后一個元素同時將其加入 queue2租谈，然后交換 queue1 和 queue2篮奄，即為 top() 操作捆愁；
將最后一個元素刪除，然后交換 queue1 和 queue2 即為 pop() 操作窟却；

621. 最大子序列
思路
用 queue 來存儲最小的前綴和的下標昼丑，連續(xù)序列長度為 k1 ~ k2，則從當前 i 開始夸赫，連續(xù)序列的第一個下標的值應在 i-k2 ~ i-k1 之間菩帝，所以要對 queue 中元素進行更新，當 i 增加時茬腿，如果 i-k1 大于queue 中第一個元素則刪除 queue 的第一個元素呼奢；
另一點是我們要的前綴和是最小，則在往queue 中加入新的下標時切平，該下標對應的前綴和應比 queue 中的最后一個小握础，因為對于當前 i 如果連續(xù)序列在滿足要求的長度范圍時，我們要使和最大則需找到最小的前綴和悴品，那這樣往隊列里添加更大的前綴和根本不起作用禀综，因為當 sum[queue.getLast() - 1] < sum[queue.getLast()] 時 sum[i] - sum[queue.getLast() - 1] > sum[i] - sum[queue.getLast()]， 這樣往 queue 中加入后面的下標明顯不起任何作用苔严，所以我們要讓 queue 中下標按對應 sum 的大小降序排列
錯誤

1. Queue 是用 LinkedList 實現(xiàn)定枷，但LinkedList 的好多功能 Queue 接口并不具備，比如本題用的 getFirst() 和 getLast() 功能届氢，所以本題隊列聲明應該這樣寫
   LinkedList<Integer> queue = new LinkedList<>();
   而不是
   Queue<Integer> queue = new LinkedList<>();
2. 在 queue.removeLast() 時要用 while 循環(huán)欠窒，用 if 會報錯

Depth First Search

211. 字符串置換
思路

1. 兩個字符轉換成字母數組，分別排序(Java 默認的排序是快排)悼沈，for 循環(huán)一一對比
   錯誤
   要注意先判斷字符串長度是否相等贱迟，不相等的情況比如 A 為空串 B 為 'a'，如果未判斷長度是否相等絮供，就對比會導致跳過 for 循環(huán) return true
2. 建立一個整數數組衣吠，統(tǒng)計字符串中字母出現(xiàn)的次數，對于字符串 A壤靶，字母每出現(xiàn)一次加一缚俏，對于字符串B，字母每出現(xiàn)一次減一贮乳，最后如果整數數組中元素值都為 0忧换，說明 A 和 B 可以相互轉換

190.下一個排列II
思路
首先應該先理解 字典序，從右往左找到第一個小于它右邊相鄰數的數向拆，該數即為需要交換的位置 Index1亚茬，該數右邊位置必然都是降序排列，從最右邊開始尋找第一個大于該數的數的位置 Index2浓恳，交換兩數刹缝，此時得到新的序列必然排在原序列之后碗暗，此時要明確從 Index1 往后的所有數全是降序排列，此時序列即為以Index1及其左邊的所有字母開頭的序列中權重最大的梢夯，從 Index1 + 1 翻轉言疗，則得到以 Index1 及其左邊的所有字母開頭的序列中權重最小的序列，即為原序列下一個排序
錯誤
邊界書寫不仔細颂砸，數組越界

52.下一個排列
思路
和上題思路一樣噪奄，只是多了需要返回數組
注意
找到 index 和 biggerIndex 后記得 break

51. 上一個排列
思路
和下一個排列過程正好反過來，從左往右尋找人乓，第一個值大于其右邊相鄰位置值的 index勤篮，然后從 index + 1 開始往右尋找第一個值小于 nums[index] 的位置，交換兩個位置的值撒蟀，然后從 index + 1 開始反轉叙谨，即得到上一個排序
錯誤
忘記了 ArrayList 讀取用 ArrayList.get()，ArrayList 修改用 ArrayList.set()

10.字符串的不同排列
思路
將當前字符串轉化為字符數組按字母從小到大排序保屯，再轉化為字符串手负，此時字符串為字典序中權值最小的值，不斷得到下一個排序加入 results姑尺，直到得到最后一個排序為止
注意
最后一個排序時 return null 作為結束標志
錯誤

1. String.valueOf(); 在進行字符串轉化時有個坑
2. 兩次尋找下標的操作不要忘記 break

Breadth First Search

433. 島嶼的個數
思路

1. for循環(huán) + bst + inBound
   for 循環(huán)遍歷布爾數組中每一個點竟终，對于值為 true (不是 1 )的點進行 bst，將 bst 中找到的所有相連的值為 true 的點布爾值全部置為 false切蟋，每 bst 一次 count 加1统捶，inBound 函數用于檢查坐標是否越界以及當前坐標對應的布爾值是否為 false

錯誤
a. 數組是布爾數組，里面的 0 和 1 代表的是 false 和 true柄粹，不是數字喘鸟，不是數字，不是數字驻右，重要事情加粗說三遍
b. 本題不是分層遍歷,所以不需要在 while (!queue.isEmpty()) 后面加 for (int i = 0; i < size; i++);

2. 并查集
   還不會

69. 二叉樹的層次遍歷
思路
典型 bfs 分層遍歷模板什黑，要寫熟

242. 將二叉樹按照層級轉化為鏈表
思路
二叉樹的分層遍歷，只不過新建一個新的 dummy 結點來記錄鏈表

618.搜索圖中結點
思路
圖的最短路徑
錯誤
應在隊列拋出結點的同時判斷結點是否是要找的結點，如果放到for 循環(huán)中對鄰接表中的點進行判斷則當圖只有一個點時會報錯

598. 僵尸矩陣
思路
for 循環(huán)統(tǒng)計人數并將僵尸的坐標全部加入隊列，然后就是典型的 bfs 分層遍歷邻寿，層數即天數，需要說明的是矩陣中的所有的僵尸位置就是 bfs 第一層
錯誤

1. for 循環(huán)矩陣對矩陣中每一個僵尸位置進行了 bfs箱熬，比如從位置 A 開始 bfs，周圍所有 People 全部變成了 Zombie，已經計算好了 days，但退出當前 bfs 后橘蜜，因為周圍原本 People 的位置都變成了 Zombie，for 循環(huán)會繼續(xù)進入新出現(xiàn)的 Zombie 位置繼續(xù) bfs付呕，雖然周圍的點都已經是 Zombie扮匠，但 days 仍舊在增加捧请，days本來不應該增加卻增加了凡涩，這樣就會出現(xiàn)錯誤
2. 必須要在 people 大小為 0 時退出 bfs 并return days棒搜，否則也會出現(xiàn)上述錯誤

611. 騎士的最短路線
思路
典型的 bfs 分層遍歷
錯誤
布爾數組里面的 0 和 1 代表的是 true 和 false，布爾數組里面的 0 和 1 代表的是 true 和 false活箕，布爾數組里面的 0 和 1 代表的是 true 和 false力麸，重要事情加粗再說三遍

531.六度問題
思路
經典的 bfs 分層遍歷模板

bugfree

605.序列重構
思路

127.拓撲排序
思路
統(tǒng)計每個結點入度，把度為 0 的結點加入隊列育韩，然后對隊列拋出的結點加入結果同時對該結點相鄰結點進行 bfs克蚂，遍歷到的結點的度減一，如果度等于 0筋讨，則加入隊列

Binary Tree & Divide Conquer

597. 具有最大平均數的子樹
思路
用分治法 + ResultType埃叭，定義ResultType來記錄當前結點的sum 和 size
錯誤
細節(jié)錯誤，再寫一遍

596. 最小子樹
思路

1. 全局變量(minSum, minRoot) + 分治
   bugfree
2. ResultType + 分治
   思路
   定義ResultType(node, minSum, sum) + 分治
   錯誤
   沒搞清 sum 實際上是用于計算葉子結點的 minSum 的悉罕，以及當前result 結點的 minSum赤屋、node 更新的判斷條件是if (leftResult.minSum <= result.minSum)和if (rightResult.minSum <= result.minSum)

480. 二叉樹的所有路徑
思路

1. 分治，將當前結點加到左子樹的每條路徑和右子樹的每條路徑上
   錯誤
   root 為空以及 root 為葉子結點時處理寫錯
2. 遍歷
   兩種方法還是手寫不太熟練

97. 二叉樹的最大深度
思路

1. 分治壁袄，計算左子樹高度类早，計算右子樹高度，兩者最大值 + 1即為二叉樹高度

bugfree

2. 遍歷

方法不會寫
遍歷要加全局變量

93. 平衡二叉樹
思路

1. 分治 + ResultType嗜逻，根據平衡二叉樹定義涩僻，左右子樹有一個不平衡則二叉樹不平衡，左右子樹高度差大于一則二叉樹不平衡
   錯誤
   判斷左右子樹是否平衡時栈顷，|| 寫成了 &&

2. 分治不加 ResultType
   不會寫

66. 二叉樹的前序遍歷

1. 分治 + 遞歸
2. 遍歷 + 遞歸
3. 非遞歸 + 棧(幾乎必考)
   思路
   先將當前結點加入棧逆日，當棧非空時拋出結點 node，結點值加入results萄凤，當 node.right 不為空時加入棧室抽， node.left 不為空時加入棧，注意加入順序是先加右兒子再左兒子

67. 二叉樹的中序遍歷

1. 分治 + 遞歸
2. 遍歷 + 遞歸
3. 非遞歸 + 棧 (幾乎必考)
   思路
   從根結點開始一直向左查找蛙卤，在向左查找過程中將查找過的結點全部加入棧狠半，直到找到最左邊的結點颤难，此時該結點值為二叉樹的中序遍歷的起始結點行嗤，結點值加入 results 已日，判斷該結點右兒子是否存在，不存在則說明是該結點是二叉樹最左的葉子結點栅屏，若存在則對以右兒子為根結點的二叉樹執(zhí)行重復操作飘千，右兒子為根結點的二叉樹的最左結點是這個二叉樹中序遍歷的第二結點堂鲜，依次類推，理解中序遍歷非遞歸做法的關鍵是理解不斷遞歸尋找最左結點的過程

68.二叉樹的后序遍歷

1. 分治 + 遞歸
2. 遍歷 + 遞歸
3. 非遞歸 + 棧(幾乎必考)
   思路
   在鏈接中寫的很詳細了缔莲，比較難記霉旗，要多看幾遍痴奏，背下來

小結：
二叉樹的前、中鸵闪、后序三種遍歷遞歸方式的兩種解法除了需要按照遍歷順序調整下左兒子檐晕、當前結點、右兒子的代碼順序蚌讼，其它幾乎一樣辟灰；重點在于非遞歸寫法，死記硬背也要記下來

453. 將二叉樹拆成鏈表
思路

88. 最近公共祖先
思路
首先搞清最近公共祖先定義啦逆，結點自己本身也是自己的祖先伞矩；
分治法，分別在左子樹和右子樹中尋找兩個結點的公共祖先夏志，左子樹和右子樹都存在則返回 root乃坤，右子樹為空則 return left，左子樹為空則 return right
錯誤
異常情況寫錯沟蔑，題目已經說明兩個結點在樹中存在湿诊，需要考慮下 root == null || root == A || root == B 情況
如果不存在 return null

474. 最近公共祖先 II
思路
因為有 parent 指針，比較好做瘦材，從當前結點 A 和 B 向上查找厅须，找到從當前結點 A 和 B 到根結點的完整路線記錄在 ArrayList 中，然后去從兩個數組的最后一個元素 (根結點) 開始一一對比食棕，找到最后一個相同的元素即為最近公共祖先
錯誤

while (indexA >= 0 && indexB >= 0) {
    if (pathA.get(indexA) != pathB.get(indexB)) {
        CA = pathA.get(indexA + 1); 
    }
    indexA--;
    indexB--;
}

這么寫當二叉樹是那種單線情況朗和，比如 {1,#,2,#,3,#,4,#,5} 尋找 3 和 5 的LCA 時，CA 會一直保持在 null 不更新簿晓，正確寫法如下：

while (indexA >= 0 && indexB >= 0) {
    if (pathA.get(indexA) != pathB.get(indexB)) {
        break;
    }
    lowestAncestor = pathA.get(indexA);
    indexA--;
    indexB--;
}

578. 最近公共祖先 III
思路
總體思路和 88. 最近公共祖先 相似眶拉，不同之處在于本題兩個結點 A 和 B 不一定在樹中出現(xiàn)，所以需要額外定義 ResultType 來記錄 A 和 B 結點是否存在
錯誤

1. 思路有點問題憔儿，確定完 A 和 B 結點的存在性后忆植，確定在以 root 為根結點的二叉樹中 A 和 B的公共祖先，分 5 種情形：
   1. A 和 B 中一個是 root 結點
   2. A 和 B 分別在 root 的左右子樹
   3. A 和 B 同時在 root 的左子樹
   4. A 和 B 同時在 root 的右子樹
   5. A 和 B 不在 root 為根結點的二叉樹中
2. root 為空時，不是return true朝刊， return false

if (root == null) {
    return new ResultType(false, false, root);
}

95. 驗證二叉查找樹
思路

1. 分治法 + ResultType(以當前結點為根結點的子樹是否平衡耀里，子樹最大值和最小值)
2. 遍歷 + 全局變量
   不會

155. 二叉樹的最小深度
思路

1. 分治
   錯誤
   忘記考慮二叉樹只有一個分支的特殊情形，比如 {1,#,2,3}
2. 遍歷
   思路
   一邊遍歷一邊記錄當前深度拾氓，遍歷到葉子結點后和全局變量進行比較冯挎，如果當前深度小于全局最小深度則更新它
   錯誤
   全局變量初始值不要寫0，否則沒辦法更新痪枫，應該寫成 private int depth = Integer.MAX_VALUE;

595. 二叉樹最長連續(xù)序列
思路

1. 分治 + ResultType(兩個變量 1. 從當前根結點出發(fā)的最長連續(xù)序列長度织堂； 2. 當前根結點構成的二叉樹的所有一子樹的各個連續(xù)序列中最長的那個)
2. 分治 + 遍歷(全局變量)

614.二叉樹的最長連續(xù)子序列 II
思路
分治 + ResultType(up 和 down)
從根結點出發(fā)向左尋找最大的 up 或 down，向右尋找最大的 up 或 down奶陈，只會出現(xiàn)兩種情形：

1. 左右兩邊一個為 up 另一個為 down，此時 max_length = up + down + 1;
2. 左右兩邊同時為 down 或者 同時為 up附较，此時 max_length = up + down + 1; 其中 up 或 down 有一個值為 0 未更新

錯誤
細節(jié)上 && 寫成 || 的小錯誤

619. 二叉樹的最長連續(xù)子序列III
思路
做法同上題類似吃粒，只是把二叉樹換成了多叉樹，所以要把 if 條件句換成 for (MultiTreeNode node : root.children) + if 條件句

378.將二叉查找樹轉換成雙鏈表
思路
分治 + ResultType(當前結點為根結點的二叉樹轉換成雙鏈表的頭尾結點)
因為是二叉查找樹拒课，分別將左子樹和右子樹轉換成雙鏈表徐勃，然后按順序和當前結點連起來，然后返回鏈表頭結點
注意

1. 要考慮左右子樹為空的情形
2. 鏈表是雙向鏈表早像，所以在連接時要記得連完 next 指針要反過來連 prev

448. 二叉樹查找樹中序后繼
思路
理解中序遍歷尋找下一個結點的 3 種情況是解題關鍵

475. 二叉樹的最大路徑和 II
思路
分治
錯誤
審題不仔細僻肖，路徑可以在二叉樹任意結點結束，所以合并代碼要這么寫 int sum = Math.max(0, Math.max(left, right)) + root.val;

Binary Search 除了414和617全部完成

459. 排序數組中最接近元素
思路
在數組中二分尋找 index (A[index] >= target)卢鹦，因為 target 不一定在數組中臀脏，可能小于 A[0]，可能大于 A[A.length - 1]冀自，也可能不是整數在A[start] 和 A[end]之間揉稚，所以要對 3 種情況做特判

458. 目標最后位置
bugfree

28. 搜索二維矩陣
思路

1. 先對行進行二分，再對列進行二分查找
2. 由于本題的矩陣特性熬粗，可將二維數組轉換成一維數組來進行二分查找

錯誤
沒記住對于mid在二維數組中坐標為x = mid / row, y = mid % col

585. 山脈序列中的最大值
思路
比較 nums[mid] 和 nums[mid + 1] 大小搀玖，來判斷當前 mid 是在上升段還是下降段
錯誤

1. 不熟時比較容易同時寫 if (nums[mid] > nums[mid - 1]) start = mid;和if (nums[mid] < nums[mid + 1]) end = mid;這種在處于峰值時會死循環(huán)的錯誤
2. 忘記要求返回的是值而不是下標

447. 在大數組中查找
思路
仍舊是尋找排序數組中目標數的第一個位置，多了用倍增方法來比較確定右邊界下標的操作
注意
讀取操作為reader.get(index)

159. 尋找旋轉排序數組中的最小值
思路
首先需要明確 數組中沒有重復元素 不然沒辦法用二分法來做驻呐，以 A[A.length - 1] 為 target灌诅，將旋轉排序數組分為兩段，判斷 mid 出現(xiàn)在哪個段含末，不斷二分縮小范圍最后鎖定在兩個分割點上

bugfree

160. 尋找旋轉排序數組中的最小值 II
思路
因為數組中可能 存在重復元素猜拾，所以當是特殊情況比如數組是 111101111 的情況下，用二分法其實是沒辦法判斷到底在哪一段答渔，此時只能用 for 循環(huán)遍歷的方法來求 min关带，需要注意的是 min 初值設定可以設為 nums[0]

63. 搜索旋轉排序數組 II
思路
同樣是只能用 for 循環(huán)遍歷，原因同上

75. 尋找峰值
思路
需要考慮四種情況：谷底、峰頂宋雏、上升段芜飘、下降段
但用if (A[mid] < A[mid + 1]) 做判斷條件后可把谷底并入上升段，峰頂并入下降段磨总，和這個 585. 山脈序列中的最大值 思路類似

bugfree

74. 第一個錯誤的代碼版本
思路
尋找排序數組 target 出現(xiàn)的第一個位置的變形題

bugfree

62. 搜索旋轉排序數組
思路

1. 笨方法是二分法兩次嗦明，第一次找到旋轉排序數組最小值下標
   index，下標 0 到 下標 index - 1 和下標 index 到下標 end 分別是段從小到大排序的數組蚪燕，判斷好 target 在哪一段娶牌，直接用二分法
   查找
   錯誤
   忘記 index - 1 在 index 為 0 時會越界，要加上 index > 0做判斷條件
2. 二分法一次
   錯誤
   忘記沒找到結果時應返回 -1

462. 目標出現(xiàn)總和
思路
在升序數組找到目標數最后一次出現(xiàn)的 lastIndex馆纳，和第一次出現(xiàn)的 firstIndex诗良，count = lastIndex - firstIndex + 1

bugfree

14. 二分查找
思路
二分法模板，找到第一個位置

bugfree

460. 在排序數組中找最接近的K個數
思路

先尋找最接近 target 的下標 index鲁驶， 以 index 和 index - 1 為起始點在不越界的情況下鉴裹，按照題目要求(將最接近 target 和 接近程度相同時的較小數排在前面)將兩邊元素不斷加入大小為 k 的數組
錯誤
思路不清晰，往結果中加入元素寫不太清楚

414. 兩個整數相除

61. 搜索區(qū)間
思路
找到第一個和最后一個位置钥弯，放到 results 數組中径荔，老套的二分法模板

bugfree

38. 搜索二維矩陣 II
思路
矩陣滿足行從小到大順序，列從小到大順序脆霎，且無重復元素总处，從左下角或者右上角開始執(zhí)行，一次排除一行或者一列
錯誤
寫得不夠熟

600. 包裹黑色像素點的最小矩形
思路
從給定點出發(fā)分別用二分法向上下找到行的邊界睛蛛，向左右找到列的邊界
area = (row2 - row1 + 1) * (col2 - col1 + 1);
如何尋找邊界需要明確：
尋找行邊界時鹦马，要對每一行判斷是否存在黑色像素點
尋找列邊界時，要對每一列判斷是否存在黑色像素點
錯誤
數組是字符二維數組玖院，所以數組中的 0 和 1 是字符菠红，要加單引號，如果不加會在檢查行列是否包含黑色像素時報錯
當然本題思路仍舊不夠清晰

457. 經典二分查找問題
思路
二分法尋找第一個位置或最后一個位置的模板都可以

bugfree

141. x的平方根
思路
如果 x < 1难菌， return 0试溯，否則從 0 到 x 進行二分
注意各個變量需要定義為 long，否則 mid * mid 會溢出
錯誤
因為取整是向下取郊酒，所以需要 return (int)start;

586. 對x開根II
思路
首先要判斷 x 是否大于 1遇绞，若 x 小于 1 則 end = 1，若 x 大于 1 則 end = x燎窘；
其次二分法退出條件是 end - start > eps 其中 eps 的精度要看要求
錯誤
小錯誤

617.最大平均值子數組
437. 書籍復印
思路
對每個人工作量進行二分摹闽，計算在當前工作量下所需要的人數，在人數滿足小于等于 k 的情況下褐健，使每個人的工作量盡可能地小
錯誤
在書寫 countCopier 函數時容易忽略下面錯誤
錯誤寫法

int sum = 0;
int copier = 1;
for (int i = 0; i < pages.length; i++) {
     sum += pages[i];
     if (sum > limit) {
          copier++;
          sum = 0;
     }
}
return copier;

正確寫法

int sum = pages[0];
int copier = 1;
for (int i = 1; i < pages.length; i++) {
    if (sum + pages[i] > limit) {
         copier++;
         sum = 0;
    }
    sum += pages[i];
}
return copier;

錯誤在于 當 sum + pages[i] > limit 時付鹿， pages[i] 的工作量本該計給下一個人澜汤，而錯誤寫法把 page[i] 計給上一個人了

183.木材加工
思路
對木頭長度進行二分，計算當前長度 length 下可以切割的木頭個數舵匾，在保證當前木頭個數大于等于 k 的情況下俊抵，使得每段木頭長度 length 盡可能長；計算木頭個數 count += L[i] / length; 坐梯；本題和上題思路類似

bugefree

strStr（全部完成）

13.strStr
思路
常規(guī)的兩層循環(huán)一一對比

錯誤
異常情況寫錯徽诲，只需考慮 source 或 target 為空情況，return -1;

594.strStr II
思路
m = target.length()吵血，求出 target 的哈希碼谎替，求出每 m 位的哈希碼，如果出現(xiàn)某 m 位的哈希碼和 target 的哈希碼相等蹋辅，則需要調用 substring 函數和 target 字母逐位比較判斷是否相等
錯誤

1. hashcode 計算 寫的不夠熟練
2. power 的計算不能忘記取模

17. Subsets
思路
遞歸 + 回溯钱贯，每一次遞歸只往list中加一個元素，定義startIndex來標記每一次遞歸的添加元素位置

錯誤

1. 異常情況中輸入是空集情況應該返回 [[]];
2. 輸出子集有順序要求晕翠，先排序

18. Subsets II
思路
比上題多了一個去重的過程喷舀，用選代表的方式增加一個判別條件
if (i != 0 && nums[i - 1] == nums[i] && i > startIndex)
錯誤
進入下一輪遞歸是help (nums, i + 1, list, results)而不是help(nums, startIndex, list, results)

15. Permutations
思路
排列問題和組合問題區(qū)別：不需要startIndex

錯誤

1. 去除重復添加操作 if (list.contains(nums[i])) {continue;}要寫在添加操作list.add(nums[i])的前面
2. 輸入為[]時，輸出為[[]]

16. Permutations II
思路
本題的去重條件if (visited[i] == 1 || (i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0))中visited[i] == 1實際上就相當于全排列的判斷條件if (list.contains(nums[i]))淋肾， 而后面的(i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0)實際上是在除下列情況：比如數組 [1, 2, 2] 第一個 2 用 A 表示，第二個 2 用 B 表示爸邢，我們在 [1, A, B] 和 [1, B, A] 兩個相同排序中選取典型的[1, A, B]做代表樊卓，所以當某一次遞歸出現(xiàn) [1, B] 開頭的排序，下一個遞歸中只有 A 未被添加杠河，但我們通過判斷條件(i != 0 && nums[i - 1] == nums[i] && visited[i - 1] == 0) continue 掉 A

錯誤
去重不會