在你還沒有拿得出手的實戰項目證明自己能力時，面試官隻能拿算法題評估你。力扣算法題因被BAT、京東、美團、字節跳動、滴滴、拼dd、微軟、亞馬遜、Google、Facebook等一線科技公司選作面試題而名聲大噪，不論你是想拿下大廠Offer，還是想在技術道路上走得更遠，刷算法題，尤其是刷力扣算法題，無疑是一個高效率的選擇。

簡單地會解某一道算法題並不意味著什麼，因為很少有人能刷完力扣的上千道題；“小抄”是指不那麼正式的筆記，算法小抄把算法題分門別類彙總，提煉出各類題的解題框架，從而以不變應萬變。

《漫畫算法》作者@程序員小灰|@stormzhang等KOL力薦。

贈LeetCode力扣Plus會員85折優惠劵。

榮獲CSDN“程序員IT好書評選”獎

2021年度京東圖書科技榜TOP 3

用喜聞樂見的語言講述算法，書中配有幾百幅有趣的算法圖示，並送上部分動畫演示。

《labuladong的算法小抄》專攻算法刷題，訓練算法思維，應對算法筆試。注重用套路和框架思維解決問題，以不變應萬變。
第1章列舉了幾個最常見的算法類型及對應的解題框架思路，包括動態規劃、回溯、廣度優先搜索及雙指針、滑動窗口等算法技巧。
第2章用動態規劃的通用思路框架解決了十幾道經典的動態規劃問題，例如，正則表達式、背包問題，同時還介紹了如何寫狀態轉移方程、如何進行狀態壓縮等技巧。
第3章介紹了數據結構相關的算法，例如，二叉樹相關題目的解法，也包括LRU、LFU這種面試常考的算法原理。
第4章介紹了回溯算法、廣度優先搜索算法等核心套路在算法題中的運用，鞏固對算法框架的理解。
第5章講解了一些高頻題目，每道題目可能會結合多種算法思路進行講解，也可能有多種解法，讀完這一章，你就可以獨自遨遊題海啦！

微信公眾號labuladong的作者，有多年的刷題經驗，希望用通俗的語言幫助廣大互聯網從業者少走彎路，快速從根本上攻克算法難關，為職業道路的發展賦能。

作為技術人，不管你是想進知名互聯網公司，還是想以後在技術的道路上走得遠，算法都是必經之路，它決定著技術人發展的上限，所以對於技術人來說，學好算法是非常非常非常必要的，那麼，有這個意識之後，這本書，就是你需要的。

——張奇，微信公眾號“stormzhang”博主

在國內外各大IT公司的面試流程中，考察候選人算法能力是極其重要的一環。刷算法題既可以提高我們的面試優勢，也充分鍛煉了我們的邏輯思維能力。labuladong的這本算法小抄，用生動的語言為我們講解了許多經典的算法題目，對想要提升算法能力的小伙伴很有幫助。

——魏夢舒（@程序員小灰），暢銷書《漫畫算法》作者，微信公眾號“程序員小灰”博主

力扣官網題號及名稱 /V

本書約定／ 1

語言基礎／ 5

第1章 核心套路篇 ／ 21
1.1 學習算法和刷題的框架思維 ／ 21
1.1.1 數據結構的存儲方式 ／ 21
1.1.2 數據結構的基本操作 ／ 23
1.1.3 算法刷題指南 ／ 25
1.1.4 最後總結 ／ 30
1.2 動態規劃解題套路框架 ／ 31
1.2.1 斐波那契數列 ／ 32
1.2.2 湊零錢問題 ／ 37
1.2.3 最後總結 ／ 42
1.3 回溯算法解題套路框架 ／ 43
1.3.1 全排列問題 ／ 43
1.3.2 N 皇後問題 ／ 48
1.3.3 最後總結 ／ 51
1.4 BFS 算法套路框架 ／ 53
1.4.1 算法框架 ／ 53
1.4.2 二叉樹的最小高度 ／ 54
1.4.3 解開密碼鎖的最少次數 ／ 56
1.5 雙指針技巧套路框架 ／ 64
1.5.1 快、慢指針的常用算法 ／ 64
1.5.2 左、右指針的常用算法 ／ 68
1.6 我寫了首詩，保你閉著眼睛都能寫出二分搜索算法 ／ 71
1.6.1 二分搜索框架 ／ 72
1.6.2 尋找一個數（基本的二分搜索） ／ 73
1.6.3 尋找左側邊界的二分搜索 ／ 75
1.6.4 尋找右側邊界的二分搜索 ／ 79
1.6.5 邏輯統一 ／ 82
1.7 我寫了一個模板，把滑動窗口算法變成了默寫題 ／ 85
1.7.1 最小覆蓋子串 ／ 87
1.7.2 字符串排列 ／ 91
1.7.3 找所有字母異位詞 ／ 93
1.7.4 最長無重復子串 ／ 94

第2章 動態規劃繫列 ／ 96
2.1 動態規劃設計：最長遞增子序列 ／ 96
2.1.1 動態規劃解法 ／ 97
2.1.2 二分搜索解法 ／ 100
2.2 二維遞增子序列：信封嵌套問題 ／ 104
2.2.1 題目概述 ／ 104
2.2.2 思路分析 ／ 105
2.2.3 最後總結 ／ 107
2.3 最大子數組問題 ／ 108
2.3.1 思路分析 ／ 108
2.3.2 最後總結 ／ 110
2.4 動態規劃答疑：最優子結構及dp 遍歷方向 ／ 111
2.4.1 最優子結構詳解 ／ 111
2.4.2 dp 數組的遍歷方向 ／ 113
2.5 經典動態規劃：最長公共子序列 ／ 117
2.6 經典動態規劃：編輯距離 ／ 123
2.6.1 思路分析 ／ 124
2.6.2 代碼詳解 ／ 125
2.6.3 動態規劃優化 ／ 129
2.6.4 擴展延伸 ／ 131
2.7 子序列問題解題模板：最長回文子序列 ／ 136
2.7.1 兩種思路 ／ 136
2.7.2 最長回文子序列 ／ 137
2.7.3 代碼實現 ／ 139
2.8 狀態壓縮：對動態規劃進行降維打擊 ／ 141
2.9 以最小插入次數構造回文串 ／ 148
2.9.1 思路分析 ／ 148
2.9.2 狀態轉移方程 ／ 149
2.9.3 代碼實現 ／ 152
2.10 動態規劃之正則表達式 ／ 155
2.10.1 思路分析 ／ 155
2.10.2 動態規劃解法 ／ 157
2.11 不同的定義產生不同的解法 ／ 162
2.11.1 第一種思路 ／ 162
2.11.2 第二種思路 ／ 165
2.11.3 最後總結 ／ 167
2.12 經典動態規劃：高樓扔雞蛋 ／ 168
2.12.1 解析題目 ／ 168
2.12.2 思路分析 ／ 169
2.12.3 疑難解答 ／ 172
2.13 經典動態規劃：高樓扔雞蛋（進階） ／ 173
2.13.1 二分搜索優化 ／ 173
2.13.2 重新定義狀態轉移 ／ 176
2.13.3 還可以再優化 ／ 180
2.14 經典動態規劃：戳氣球問題 ／ 181
2.14.1 回溯思路 ／ 181
2.14.2 動態規劃思路 ／ 182
2.14.3 寫出代碼 ／ 185
2.15 經典動態規劃：0-1 背包問題 ／ 188
2.16 經典動態規劃：子集背包問題 ／ 192
2.16.1 問題分析 ／ 192
2.16.2 思路分析 ／ 193
2.16.3 進行狀態壓縮 ／ 194
2.17 經典動態規劃：完全背包問題 ／ 196
2.18 題目千百變，套路不會變 ／ 200
2.18.1 線性排列情況 ／ 200
2.18.2 環形排列情況 ／ 203
2.18.3 樹形排列情況 ／ 205
2.19 動態規劃和回溯算法，到底是什麼關繫 ／ 207
2.19.1 回溯思路 ／ 207
2.19.2 消除重疊子問題 ／ 210
2.19.3 動態規劃 ／ 211

第3章 數據結構繫列 ／ 216
3.1 手把手教你寫 LRU 緩存淘汰算法 ／ 216
3.1.1 LRU 算法描述 ／ 218
3.1.2 LRU 算法設計 ／ 219
3.1.3 代碼實現 ／ 220
3.2 層層拆解，帶你手寫LFU 算法 ／ 227
3.2.1 算法描述 ／ 227
3.2.2 思路分析 ／ 228
3.2.3 代碼框架 ／ 230
3.2.4 LFU 核心邏輯 ／ 232
3.3 二叉搜索樹操作集錦 ／ 235
3.3.1 判斷 BST 的合法性 ／ 236
3.3.2 在 BST 中查找一個數是否存在 ／ 238
3.3.3 在 BST 中插入一個數 ／ 239
3.3.4 在 BST 中刪除一個數 ／ 239
3.4 完全二叉樹的節點數為什麼那麼難算 ／ 243
3.4.1 思路分析 ／ 244
3.4.2 復雜度分析 ／ 245
3.5 用各種遍歷框架序列化和反序列化二叉樹 ／ 247
3.5.1 題目描述 ／ 247
3.5.2 前序遍歷解法 ／ 248
3.5.3 後序遍歷解法 ／ 252
3.5.4 中序遍歷解法 ／ 255
3.5.5 層級遍歷解法 ／ 255
3.6 Git 原理之二叉樹最近公共祖先 ／ 260
3.6.1 二叉樹的最近公共祖先 ／ 261
3.6.2 思路分析 ／ 263
3.7 特殊數據結構：單調棧 ／ 266
3.7.1 單調棧解題模板 ／ 266
3.7.2 題目變形 ／ 268
3.7.3 如何處理循環數組 ／ 268
3.8 特殊數據結構：單調隊列 ／ 271
3.8.1 搭建解題框架 ／ 271
3.8.2 實現單調隊列數據結構 ／ 273
3.8.3 算法復雜度分析 ／ 276
3.9 如何判斷回文鏈表 ／ 277
3.9.1 判斷回文單鏈表 ／ 277
3.9.2 優化空間復雜度 ／ 280
3.9.3 最後總結 ／ 282
3.10 秀操作之純遞歸反轉鏈表 ／ 283
3.10.1 遞歸反轉整個鏈表 ／ 283
3.10.2 反轉鏈表前N 個節點 ／ 286
3.10.3 反轉鏈表的一部分 ／ 287
3.10.4 最後總結 ／ 288
3.11 秀操作之k 個一組反轉鏈表 ／ 289
3.11.1 分析問題 ／ 289
3.11.2 代碼實現 ／ 291
3.11.3 最後總結 ／ 292

第4章 算法思維繫列 ／ 293
4.1 回溯算法解決子集、組合、排列問題 ／ 293
4.1.1 子集 ／ 293
4.1.2 組合 ／ 297
4.1.3 排列 ／ 299
4.2 回溯算法最佳實踐：解數獨 ／ 301
4.2.1 直觀感受 ／ 301
4.2.2 代碼實現 ／ 301
4.3 回溯算法最佳實踐：括號生成 ／ 306
4.4 BFS 算法暴力破解各種智力題 ／ 310
4.4.1 題目解析 ／ 311
4.4.2 思路分析 ／ 311
4.5 2Sum 問題的核心思想 ／ 315
4.5.1 2Sum I ／ 315
4.5.2 2Sum II ／ 316
4.5.3 最後總結 ／ 318
4.6 一個函數解決 nSum 問題 ／ 319
4.6.1 2Sum 問題 ／ 319
4.6.2 3Sum 問題 ／ 322
4.6.3 4Sum 問題 ／ 324
4.6.4 100Sum 問題 ／ 325
4.7 拆解復雜問題：實現計算器 ／ 328
4.7.1 字符串轉整數 ／ 328
4.7.2 處理加減法 ／ 329
4.7.3 處理乘除法 ／ 331
4.7.4 處理括號 ／ 333
4.7.5 最後總結 ／ 336
4.8 攤燒餅也得有點遞歸思維 ／ 337
4.8.1 思路分析 ／ 338
4.8.2 代碼實現 ／ 339
4.9 前綴和技巧解決子數組問題 ／ 341
4.9.1 什麼是前綴和 ／ 341
4.9.2 優化解法 ／ 343
4.9.3 最後總結 ／ 344
4.10 扁平化嵌套列表 ／ 345
4.10.1 題目描述 ／ 345
4.10.2 解題思路 ／ 346
4.10.3 進階思路 ／ 349

第5章 高頻面試繫列 ／ 351
5.1 如何高效尋找素數 ／ 351
5.2 如何高效進行模冪運算 ／ 355
5.2.1 如何處理數組指數 ／ 355
5.2.2 如何處理 mod 運算 ／ 356
5.2.3 如何高效求冪 ／ 358
5.3 如何運用二分搜索算法 ／ 360
5.3.1 問題分析 ／ 360
5.3.2 擴展延伸 ／ 362
5.4 如何高效解決接雨水問題 ／ 364
5.5 如何去除有序數組素 ／ 371
5.6 如何尋找最長回文子串 ／ 373
5.7 如何運用貪心思想玩跳躍遊戲 ／ 376
5.8 如何運用貪心算法做時間管理 ／ 381
5.9 如何判定括號合法性 ／ 386
5.10 如何調度考生的座位 ／ 389
5.11 Union-Find 算法詳解 ／ 396

前言

數據結構和算法在計算機知識體繫中有著舉足輕重的作用，這塊知識也有非常經典的教材供我們學習。但是，我們刷的算法題往往會在經典的算法思想之上套層“皮”，所以很容易讓人產生一種感覺：數據結構和算法我以前學得挺好的，為啥這些算法題我完全沒思路呢？

面對這種疑惑，有人可能會擺出好幾本與算法相關的大部頭，建議你去進修。

有些書確實很經典，但我覺得咱應該搞清楚自己的目的是什麼。如果你是學生，對算法有濃厚的興趣，甚至說以後準備搞這方面的研究，那我覺得你可以去啃一啃大部頭；但事實是，大部分人（包括我）學習算法是為了應對考試，這種情況下去啃大部頭顯然就得不償失了，更高效的方法是直接刷題。

但是，刷題也是有技巧的，刷題平臺上動輒幾千道題，難道你要全刷完嗎？最高效的刷題方式是邊刷邊歸納總結，抽像出每種題型的套路框架，以不變應萬變。

我個人還是挺喜歡刷題的，經過長時間的積累、總結，沉澱出了這本書，希望能給你帶來思路上的啟發和指導。

本書特色

本書會先幫你抽像總結出框架套路，然後通過題目實踐，這應該是最高效的學習方式。即學即用，立即反饋，相信本書會讓你一讀就停不下來。

本書定位

這不是一本數據結構和算法的入門書，而是一本刷算法題的參考書。

本書的目的是手把手帶你刷題，每看完一節內容，就可以去刷幾道題，知其然，也知其所以然。