labuladong的算法筆記：Github 115K star的硬核算法教程

本書專攻算法刷題，訓練算法思維，應對算法筆試，注重用套路和框架思維解決問題，以不變應萬變。

第1章列舉了幾個最常見的算法類型及對應的解題框架思路，包括雙指標、滑動視窗等算法技巧，並把動態規劃、回溯算法、廣度優先搜索等技巧的核心抽象為二叉樹的兩種問題形式。

第2章介紹了基礎資料結構相關的算法，包括陣列鏈表的常見技巧匯總和資料結構設計的經典例題。

第3章從二叉樹的幾種解題思路開始，嘗試從二叉樹的視角理解快速排序和歸併排序，進一步講解回溯、DFS、BFS等暴力搜索算法。

第4章具體介紹了動態規劃相關的技巧，例如如何確定base case，如何寫狀態轉移方程，如何進行狀態壓縮等技巧，並用動態規劃的通用思路框架解決了十幾道經典的動態規劃問題。

第5章講解了一些高頻面試/筆試題目，每道題目可能會結合之前章節講過的多種算法思路，也可能有多種解法。讀完這一章，你就可以獨自遨遊題海啦！

Labuladong
 
有多年的刷題經驗，希望用通俗的語言説明廣大互聯網從業者少走彎路，快速從根本上攻克演算法難關，為職業道路的發展賦能。

本書約定 / 1
程式設計語言基礎 / 4

第1章 核心框架篇 / 15
1.1 學習數據結構和算法的框架思維 15
1.1.1 數據結構的存儲方式 16
1.1.2 數據結構的基本操作 17
1.1.3 算法刷題指南 18
1.2 計算機算法的本質 24
1.2.1 算法的本質 24
1.2.2 數組/ 單鏈表系列算法 26
1.2.3 二叉樹系列算法 28
1.2.4 最後總結 33
1.3 動態規劃解題套路框架 33
1.3.1 斐波那契數列 35
1.3.2 湊零錢問題 40
1.3.3 最後總結 45
1.4 回溯算法解題套路框架 46
1.4.1 全排列問題 47
1.4.2 N皇后問題 52
1.4.3 最後總結 55
1.5 BFS算法解題套路框架 55
1.5.1 算法框架 56
1.5.2 二叉樹的最小高度 57
1.5.3 解開密碼鎖的最少次數 59
1.5.4 雙向BFS 優化 62
1.6 手把手帶你刷二叉樹（綱領） 65
1.6.1 二叉樹的重要性 66
1.6.2 深入理解前、中、後序 67
1.6.3 兩種解題思路 71
1.6.4 後序位置的特殊之處 75
1.6.5 層序遍歷 79
1.7 我寫了首詩，保你閉著眼睛都能寫出二分搜索算法 81
1.7.1 二分搜索框架 82
1.7.2 尋找一個數（基本的二分搜索） 82
1.7.3 尋找左側邊界的二分搜索 84
1.7.4 尋找右側邊界的二分搜索 88
1.7.5 邏輯統一 90
1.8 我寫了一個範本，把滑動視窗算法變成了默寫題 93
1.8.1 最小覆蓋子串 96
1.8.2 字串排列 100
1.8.3 找所有字母異位元詞 102
1.8.4 最長無重複子串 103

第2章 手把手刷數據結構 / 105
2.1 數組、鏈表 105
2.1.1 單鏈表的六大解題套路 105
2.1.2 數組雙指針的解題套路 116
2.1.3 小而美的算法技巧：首碼和數組 124
2.1.4 小而美的算法技巧：差分數組 128
2.2 數據結構設計 134
2.2.1 算法就像搭樂高：帶你手寫LRU算法 135
2.2.2 算法就像搭樂高：帶你手寫LFU算法 144
2.2.3 以O(1) 時間複雜度刪除/ 查找數組中的任意元素 151
2.2.4 單調棧結構解決三道算法題 159
2.2.5 單調佇列結構解決滑動視窗問題 164

第3章 手把手培養算法思維 / 170
3.1 二叉樹 170
3.1.1 手把手帶你刷二叉樹（思路） 170
3.1.2 手把手帶你刷二叉樹（構造） 179
3.1.3 手把手帶你刷二叉樹（序列化） 192
3.1.3 零、前/ 中/ 後序和二叉樹的唯一性 193
3.1.4 歸併排序詳解及運用 206
3.2 二叉搜尋樹 215
3.2.1 手把手帶你刷二叉搜尋樹（特性應用） 215
3.2.2 手把手帶你刷二叉搜尋樹（增刪查改） 220
3.2.3 快速排序詳解及運用 227
3.3 圖論算法 237
3.3.1 圖論算法基礎 237
3.3.2 Union-Find算法詳解 245
3.3.3 最小生成樹之 Kruskal算法 259
3.4 暴力搜索算法 268
3.4.1 回溯算法解決子集、排列、組合問題 268
3.4.2 經典回溯算法：集合劃分問題 291
3.4.3 DFS算法搞定島嶼系列題目 305
3.4.4 BFS算法解決智力遊戲 317

第4章 手把手刷動態規劃 / 323
4.1 動態規劃核心原理 323
4.1.1 base case 和備忘錄的初始值怎麼定 323
4.1.2 最優子結構和dp 數組的遍歷方向怎麼定 329
4.1.3 算法時空複雜度分析實用指南 338
4.1.4 動態規劃的降維打擊：空間壓縮技巧 351
4.2 子序列類型問題 358
4.2.1 動態規劃設計：最長遞增子序列 358
4.2.2 詳解最大子數組和 367
4.2.3 詳解編輯距離問題 372
4.2.4 詳解最長公共子序列問題 381
4.2.5 詳解正則匹配問題 389
4.2.6 子序列問題解題範本 397
4.3 背包問題 404
4.3.1 0-1 背包問題解題框架 404
4.3.2 背包問題變體之子集分割 407
4.3.3 背包問題之零錢兌換 410
4.4 用動態規劃玩遊戲 414
4.4.1 最小路徑和問題 414
4.4.2 動態規劃算法通關《魔塔》 419
4.4.3 高樓扔雞蛋問題 426
4.4.4 戳氣球問題 438

第5章 高頻面試系列 / 445
5.1 鏈表操作的遞迴思維一覽 445
5.1.1 遞迴反轉整個鏈表 446
5.1.2 反轉鏈表前N 個節點 448
5.1.3 反轉鏈表的一部分 449
5.2 田忌賽馬背後的算法決策 450
5.3 一道數組去重的算法題把我整蒙了 454
5.4 帶權重的隨機選擇算法 458
5.4.1 解法思路 459
5.4.2 解法代碼 460
5.5 二分搜索題型套路分析 462
5.5.1 原始的二分搜索代碼 463
5.5.2 二分搜索問題的泛化 465
5.5.3 運用二分搜索的套路框架 467
5.5.4 例題一：珂珂吃香蕉 468
5.5.5 例題二：運送貨物 471
5.5.6 例題三：分割數組 474
5.6 如何高效解決接雨水問題 475
5.6.1 核心思路 476
5.6.2 備忘錄優化 478
5.6.3 雙指針解法 479
5.6.4 擴展延伸 481
5.7 一個函數解決nSum 問題 483
5.7.1 twoSum 問題 483
5.7.2 3Sum 問題 486
5.7.3 4Sum 問題 488
5.7.4 100Sum 問題 489
5.8 一個方法解決最近公共祖先問題 491
5.8.1 尋找一個元素 492
5.8.2 解決五道題目 49