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

前言 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