JavaScript算法：基本原理與代碼實(shí)現(xiàn)

前言 6
第 1 章 時(shí)間復(fù)雜度與空間復(fù)雜度 10
1.1 時(shí)間復(fù)雜度 10
1.2 空間復(fù)雜度 15
1.3 總結(jié) 17
1. 時(shí)間復(fù)雜度 17
2. 空間復(fù)雜度 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 快速排序的優(yōu)化 52
2.7.3 非遞歸實(shí)現(xiàn) 54
2.7.4 算法比較 55
2.7.5 快速排序的一些應(yīng)用 55
2.8 計(jì)數(shù)排序 56
2.9 桶排序 58
2.10 基數(shù)排序 61
2.10.1 LSD 基數(shù)排序 61
2.10.2 MSD 基數(shù)排序 64
2.10.3 字符串使用基數(shù)排序?qū)崿F(xiàn)字典排序 66
2.11 總結(jié) 68
2.11.1 算法使用場景 69
第 3 章 線性結(jié)構(gòu) 71
3.1 數(shù)據(jù)結(jié)構(gòu)的分類 71
3.2 數(shù)組 73
3.3 鏈表 75
3.3.1 單向鏈表 75
3.3.2 雙向鏈表 78
3.3.3 有序鏈表 80
3.3.4 循環(huán)雙向鏈表 83
3.3.5 鏈表排序 88
3.4 棧 96
3.4.1 棧的特點(diǎn)和相關(guān)概念 96
3.4.2 棧相關(guān)的方法 98
3.4.3 棧的應(yīng)用場景 99
3.5 隊(duì)列 106
3.5.1 隊(duì)列的常用方法 107
3.5.2 隊(duì)列的典型應(yīng)用 108
3.6 散列簡述 109
3.6.1 散列函數(shù) 109
3.6.2 散列沖突的解決方案 112
3.6.3 散列的應(yīng)用 121
3.7 位圖 124
3.7.1 位圖簡述 124
3.7.2 位圖的應(yīng)用 127
3.8 塊狀鏈表 129
3.8.1 塊狀鏈表簡介 129
3.8.2 塊狀鏈表的操作 130
3.9 總結(jié) 136
第 4 章 散列詳談 139
4.1 散列的定義 139
4.2 常見的散列算法 139
4.3 散列沖突的解決方案 141
4.3.1 開散列方法 142
4.3.2 閉散列方法 144
4.4 散列的應(yīng)用 146
4.4.1 數(shù)組去重 146
4.4.2 求只出現(xiàn)一次的數(shù)字 147
4.4.3 兩數(shù)之和 147
4.5 小結(jié) 148
第 5 章 樹與二叉樹 149
5.1 樹的簡介 149
5.1.1 樹的常用術(shù)語 149
5.1.2 樹的表示方式 151
5.2 二叉樹 152
5.2.2 樹的查找操作 157
5.2.3 樹的刪除操作 158
5.2.4 獲得樹的結(jié)點(diǎn)數(shù) 160
5.2.5 獲得樹的高度 161
5.2.6 樹的深度優(yōu)先遍歷 161
5.2.7 深度優(yōu)先遍歷的遞歸實(shí)現(xiàn) 163
5.2.8 深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn) 167
5.2.9 深度優(yōu)先遍歷的非遞歸實(shí)現(xiàn)的優(yōu)化 173
5.2.10 樹的廣度優(yōu)先遍歷 176
5.2.11 樹的打印 177
5.3 二叉查找樹 186
5.3.1 BST 的插入與查找操作 187
5.3.2 前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn) 188
5.3.3 BST 的移除操作 190
5.4 總結(jié) 192
第 6 章堆與優(yōu)先隊(duì)列 194
6.1 二叉堆 194
6.2 堆排序 196
6.3 topK 問題 203
6.4 優(yōu)先隊(duì)列 205
6.5 丑數(shù) 208
6.6 小結(jié) 210
第 7 章 并查集 210
7.1 沒有優(yōu)化的并查集 210
7.2 快速合并，慢查找 214
7.3 基于重量的快速合并，快速查找 218
7.4 基于深度的快速合并，快速查找 220
7.5 基于深度與路徑壓縮的快速合并，快速查找 223
7.6 相關(guān)問題 226
7.6.1 朋友圈 226
7.6.2 島嶼的數(shù)量 228
7.6.3 賬戶合并 229
7.6.4 團(tuán)伙問題 232
7.6.5 食物鏈 233
7.7 總結(jié) 235
第 8 章 線段樹 237
8.1 普通線段樹 237
8.1.1 構(gòu)建 237
8.1.2 單點(diǎn)查詢 240
8.1.3 單點(diǎn)修改 240
8.1.4 區(qū)間查詢 242
8.1.5 區(qū)間修改 243
8.1.6 延遲標(biāo)記 244
8.2 ZKW 線段樹 247
8.2.1 構(gòu)建 247
8.2.2 單點(diǎn)查詢 248
8.2.3 單點(diǎn)修改 249
8.2.4 區(qū)間查詢 249
8.3 標(biāo)記永久化技巧 251
8.3.1 基于標(biāo)記永久化的區(qū)間修改 251
8.3.2 基于標(biāo)記永久化的區(qū)間查詢 252
8.4 差分思想 253
8.4.1 基于差分思想的區(qū)間修改 254
8.4.2 基于差分思想的區(qū)間查詢 255
8.5 總結(jié) 255
第 9 章 樹狀數(shù)組 256
9.1 原理 256
9.2 構(gòu)建 262
9.3 單點(diǎn)查詢 263
9.4 單點(diǎn)修改 264
9.5 求前 n 項(xiàng)之和 265
9.6 求 a~b 項(xiàng)之和 266
9.7 區(qū)間更新 266
9.8 區(qū)間最值 266
9.9 求逆序數(shù) 269
9.10 數(shù)組離散化 269
9.11 總結(jié) 273
第 10 章 前綴樹 274
10.1 原理 274
10.2 插入字符串 275
10.3 移除字符串 277
10.4 是否包含某個(gè)字符串 277
10.5 是否包含某個(gè)前綴 278
10.6 統(tǒng)計(jì)某個(gè)字符串出現(xiàn)的次數(shù) 278
10.7 統(tǒng)計(jì)某個(gè)前綴出現(xiàn)的次數(shù) 279
10.8 優(yōu)化 279
10.9 排序 280
10.10 求最長公共前綴 282
10.11 模糊搜索 283
10.12 總結(jié) 284
第 11 章 跳表 286
11.1 跳表的結(jié)構(gòu) 286
11.2 跳表的性質(zhì) 286
11.3 插入 287
11.4 查找 289
11.5 刪除 290
11.6 得到排序數(shù)組 291
11.7 總結(jié) 291
第 12 章 簡單平衡樹 293
12.1 有旋 Treap 293
12.1.1 旋轉(zhuǎn) 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 根據(jù)排名找對應(yīng)的數(shù) 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 根據(jù)排名找對應(yīng)的數(shù) 315
12.2.8 求前驅(qū)后繼 315
12.2.9 求最大最小值 316
12.3 伸展樹 317
12.3.2 查找 323
12.3.3 插入 323
12.3.4 刪除 325
12.3.5 區(qū)間刪除 326
12.3.6 獲取 value 的排名 327
12.3.7 根據(jù)排名找對應(yīng)的數(shù) 327
12.3.8 求最大最小值 327
12.3.9 求前驅(qū)后繼 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 重構(gòu) 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 中央擴(kuò)展法 368
13.2.2 馬拉車算法 369
13.2.3 回文自動(dòng)機(jī) 375
13.2.4 后綴自動(dòng)機(jī) 382
13.3 總結(jié) 397
第 14 章 回溯算法 398
14.1 回溯算法的格式 398
14.2 子集問題的相關(guān)例題 400
14.2.1 沒重復(fù)元素的子集問題 400
14.2.2 有重復(fù)元素的子集問題 401
14.2.3 有重復(fù)元素的組合總和 402
14.2.4 無重復(fù)元素的組合總和 403
14.2.5 背包問題 404
14.2.6 裝載問題 405
14.2.7 火柴拼棍擺正方形 406
14.3 排列問題的相關(guān)例題 408
14.3.1 全排列問題 408
14.3.2 素?cái)?shù)環(huán) 409
14.3.3 批作業(yè)調(diào)度問題 411
14.3.4 八皇后問題 413
14.4 總結(jié) 415
第 15 章 動(dòng)態(tài)規(guī)劃 416
15.1 斐波那契數(shù)列 416
15.1.1 暴力法 417
15.1.2 記憶化搜索 417
15.1.3 動(dòng)態(tài)規(guī)劃法 418
15.2 找零錢 419
15.3 最長不下降子序列 421
15.4 最長公共子序列 423
15.5 爬樓梯 426
15.6 背包問題 427
15.7 總結(jié) 428