JavaScript 算法：基本原理與代碼實現

司徒正美（真名鐘欽成）

著名的JavaScript專家，曾在去哪兒網擔任前端架構師，立誌做考古學家的日語系工程師，穿梭於二次元與二進制間的“魔法師”，做過陶藝，寫過小說，涉獵Java、Ruby、JavaScript，常年活躍在開源社區，曾出版《JavaScript框架設計》一書。

李曉晨

資深前端工程師，曾在美團、快手任職，對算法、基礎框架、互動技術、DX有一定研究，最近對Web 3產生了濃厚的興趣。

前言 6

第 1 章 時間復雜度與空間復雜度 10

1.1 時間復雜度 10

1.2 空間復雜度 15

1.3 總結 17

1. 時間復雜度 17

2. 空間復雜度 18

第 2 章 排序算法 19

2.1 冒泡排序 20

2.2 選擇排序 27

2.3 插入排序 29

2.4 希爾排序 33

2.5 歸並排序 39

2.6 堆排序 47

2.7 快速排序 47

2.7.1 快速排序的常用方法 47

2.7.2 快速排序的優化 52

2.7.3 非遞歸實現 54

2.7.4 算法比較 55

2.7.5 快速排序的一些應用 55

2.8 計數排序 56

2.9 桶排序 58

2.10 基數排序 61

2.10.1 LSD 基數排序 61

2.10.2 MSD 基數排序 64

2.10.3 字符串使用基數排序實現字典排序 66

2.11 總結 68

2.11.1 算法使用場景 69

第 3 章 線性結構 71

3.1 數據結構的分類 71

3.2 數組 73

3.3 鏈表 75

3.3.1 單向鏈表 75

3.3.2 雙向鏈表 78

3.3.3 有序鏈表 80

3.3.4 循環雙向鏈表 83

3.3.5 鏈表排序 88

3.4 棧 96

3.4.1 棧的特點和相關概念 96

3.4.2 棧相關的方法 98

3.4.3 棧的應用場景 99

3.5 隊列 106

3.5.1 隊列的常用方法 107

3.5.2 隊列的典型應用 108

3.6 散列簡述 109

3.6.1 散列函數 109

3.6.2 散列沖突的解決方案 112

3.6.3 散列的應用 121

3.7 位圖 124

3.7.1 位圖簡述 124

3.7.2 位圖的應用 127

3.8 塊狀鏈表 129

3.8.1 塊狀鏈表簡介 129

3.8.2 塊狀鏈表的操作 130

3.9 總結 136

第 4 章 散列詳談 139

4.1 散列的定義 139

4.2 常見的散列算法 139

4.3 散列沖突的解決方案 141

4.3.1 開散列方法 142

4.3.2 閉散列方法 144

4.4 散列的應用 146

4.4.1 數組去重 146

4.4.2 求只出現一次的數字 147

4.4.3 兩數之和 147

4.5 小結 148

第 5 章 樹與二叉樹 149

5.1 樹的簡介 149

5.1.1 樹的常用術語 149

5.1.2 樹的表示方式 151

5.2 二叉樹 152

5.2.2 樹的查找操作 157

5.2.3 樹的刪除操作 158

5.2.4 獲得樹的結點數 160

5.2.5 獲得樹的高度 161

5.2.6 樹的深度優先遍歷 161

5.2.7 深度優先遍歷的遞歸實現 163

5.2.8 深度優先遍歷的非遞歸實現 167

5.2.9 深度優先遍歷的非遞歸實現的優化 173

5.2.10 樹的廣度優先遍歷 176

5.2.11 樹的打印 177

5.3 二叉查找樹 186

5.3.1 BST 的插入與查找操作 187

5.3.2 前驅結點與後繼結點 188

5.3.3 BST 的移除操作 190

5.4 總結 192

第 6 章堆與優先隊列 194

6.1 二叉堆 194

6.2 堆排序 196

6.3 topK 問題 203

6.4 優先隊列 205

6.5 醜數 208

6.6 小結 210

第 7 章 並查集 210

7.1 沒有優化的並查集 210

7.2 快速合並，慢查找 214

7.3 基於重量的快速合並，快速查找 218

7.4 基於深度的快速合並，快速查找 220

7.5 基於深度與路徑壓縮的快速合並，快速查找 223

7.6 相關問題 226

7.6.1 朋友圈 226

7.6.2 島嶼的數量 228

7.6.3 賬戶合並 229

7.6.4 團夥問題 232

7.6.5 食物鏈 233

7.7 總結 235

第 8 章 線段樹 237

8.1 普通線段樹 237

8.1.1 構建 237

8.1.2 單點查詢 240

8.1.3 單點修改 240

8.1.4 區間查詢 242

8.1.5 區間修改 243

8.1.6 延遲標記 244

8.2 ZKW 線段樹 247

8.2.1 構建 247

8.2.2 單點查詢 248

8.2.3 單點修改 249

8.2.4 區間查詢 249

8.3 標記永久化技巧 251

8.3.1 基於標記永久化的區間修改 251

8.3.2 基於標記永久化的區間查詢 252

8.4 差分思想 253

8.4.1 基於差分思想的區間修改 254

8.4.2 基於差分思想的區間查詢 255

8.5 總結 255

第 9 章 樹狀數組 256

9.1 原理 256

9.2 構建 262

9.3 單點查詢 263

9.4 單點修改 264

9.5 求前 n 項之和 265

9.6 求 a~b 項之和 266

9.7 區間更新 266

9.8 區間最值 266

9.9 求逆序數 269

9.10 數組離散化 269

9.11 總結 273

第 10 章 前綴樹 274

10.1 原理 274

10.2 插入字符串 275

10.3 移除字符串 277

10.4 是否包含某個字符串 277

10.5 是否包含某個前綴 278

10.6 統計某個字符串出現的次數 278

10.7 統計某個前綴出現的次數 279

10.8 優化 279

10.9 排序 280

10.10 求最長公共前綴 282

10.11 模糊搜索 283

10.12 總結 284

第 11 章 跳錶 286

11.1 跳錶的結構 286

11.2 跳錶的性質 286

11.3 插入 287

11.4 查找 289

11.5 刪除 290

11.6 得到排序數組 291

11.7 總結 291

第 12 章 簡單平衡樹 293

12.1 有旋 Treap 293

12.1.1 旋轉 294

12.1.2 插入 297

12.1.3 查找 299

12.1.4 刪除 299

12.1.5 各種遍歷 301

12.1.6 獲取 value 的排名 302

12.1.7 根據排名找對應的數 302

12.2 無旋 Treap 304

12.2.1 合並 305

12.2.2 拆分 309

12.2.3 添加 313

12.2.4 移除 314

12.2.5 查找 314

12.2.6 獲取 value 的排名 314

12.2.7 根據排名找對應的數 315

12.2.8 求前驅後繼 315

12.2.9 求最大最小值 316

12.3 伸展樹 317

12.3.2 查找 323

12.3.3 插入 323

12.3.4 刪除 325

12.3.5 區間刪除 326

12.3.6 獲取 value 的排名 327

12.3.7 根據排名找對應的數 327

12.3.8 求最大最小值 327

12.3.9 求前驅後繼 328

12.3.10 合並 328

12.3.11 拆分 328

12.4 SBT 330

12.4.1 插入 332

12.4.2 刪除 334

12.4.3 平衡 335

12.5 替罪羊樹 341

12.5.1 插入 343

12.5.2 重構 345

12.5.3 查找 348

12.5.4 刪除 348

第 13 章 字符串算法 350

13.1 匹配算法 350

13.1.1 Brute‐Force 算法 350

13.1.2 KMP 算法 350

13.1.3 多模式匹配算法 361

13.2 迴文算法 367

13.2.1 中央擴展法 368

13.2.2 馬拉車算法 369

13.2.3 迴文自動機 375

13.2.4 後綴自動機 382

13.3 總結 397

第 14 章 回溯算法 398

14.1 回溯算法的格式 398

14.2 子集問題的相關例題 400

14.2.1 沒重復元素的子集問題 400

14.2.2 有重復元素的子集問題 401

14.2.3 有重復元素的組合總和 402

14.2.4 無重復元素的組合總和 403

14.2.5 背包問題 404

14.2.6 裝載問題 405

14.2.7 火柴拼棍擺正方形 406

14.3 排列問題的相關例題 408

14.3.1 全排列問題 408

14.3.2 素數環 409

14.3.3 批作業調度問題 411

14.3.4 八皇後問題 413

14.4 總結 415

第 15 章 動態規劃 416

15.1 斐波那契數列 416

15.1.1 暴力法 417

15.1.2 記憶化搜索 417

15.1.3 動態規劃法 418

15.2 找零錢 419

15.3 最長不下降子序列 421

15.4 最長公共子序列 423

15.5 爬樓梯 426

15.6 背包問題 427

15.7 總結 428