labuladong的算法小抄

《labuladong的算法小抄》由電子工業出版社於2021年1月出版，作者是付東來（@labuladong）。本書用喜聞樂見的語言講述算法，書中配有幾百幅有趣的算法圖示，並送上部分動畫演示。

基本介紹

• 中文名：labuladong的算法小抄
• 作者：付東來（@labuladong）
• 出版社：電子工業出版社
• 出版時間：2021年1月
• 頁數：432 頁
• 定價：99 元
• 開本：16 開
• ISBN：9787121399336

內容簡介

《labuladong的算法小抄》專攻算法刷題，訓練算法思維，應對算法筆試。注重用套路和框架思維解決問題，以不變應萬變。

第1章列舉了幾個最常見的算法類型及對應的解題框架思路，包括動態規劃、回溯、廣度優先搜尋及雙指針、滑動視窗等算法技巧。

第2章用動態規劃的通用思路框架解決了十幾道經典的動態規劃問題，例如，正則表達式、背包問題，同時還介紹了如何寫狀態轉移方程、如何進行狀態壓縮等技巧。

第3章介紹了數據結構相關的算法，例如，二叉樹相關題目的解法，也包括LRU、LFU這種面試常考的算法原理。

第4章介紹了回溯算法、廣度優先搜尋算法等核心套路在算法題中的運用，鞏固對算法框架的理解。

第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.4.1 核心思路 ／ 364

5.4.2 備忘錄最佳化 ／ 366

5.4.3 雙指針解法 ／ 367

5.5 如何去除有序數組的重複元素 ／ 371

5.6 如何尋找最長回文子串 ／ 373

5.6.1 思考 ／ 373

5.6.2 代碼實現 ／ 374

5.7 如何運用貪心思想玩跳躍遊戲 ／ 376

5.7.1 跳躍遊戲 I ／ 376

5.7.2 跳躍遊戲 II ／ 377

5.8 如何運用貪心算法做時間管理 ／ 381

5.8.1 問題概述 ／ 381

5.8.2 貪心解法 ／ 381

5.8.3 套用舉例 ／ 383

5.9 如何判定括弧合法性 ／ 386

5.9.1 處理一種括弧 ／ 386

5.9.2 處理多種括弧 ／ 387

5.10 如何調度考生的座位 ／ 389

5.10.1 思路分析 ／ 390

5.10.2 簡化問題 ／ 391

5.10.3 進階問題 ／ 393

5.10.4 最後總結 ／ 395

5.11 Union-Find 算法詳解 ／ 396

5.11.1 問題介紹 ／ 396

5.11.2 基本思路 ／ 397

5.11.3 平衡性最佳化 ／ 400

5.11.4 路徑壓縮 ／ 402

5.11.5 最後總結 ／ 405

5.12 Union-Find 算法套用 ／ 407

5.12.1 DFS 的替代方案 ／ 407

5.12.2 判定合法等式 ／ 412

5.12.3 最後總結 ／ 413

5.13 一行代碼就能解決的算法題 ／ 414

5.13.1 Nim 遊戲 ／ 414

5.13.2 石子遊戲 ／ 415

5.13.3 電燈開關問題 ／ 416

作者簡介

付東來

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