前言 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 快速排序的優(yōu)化 52
2.7.3 非遞歸實現(xiàn) 54
2.7.4 算法比較 55
2.7.5 快速排序的一些應用 55
2.8 計數(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ù)排序實現(xiàn)字典排序 66
2.11 總結 68
2.11.1 算法使用場景 69
第 3 章 線性結構 71
3.1 數(shù)據結構的分類 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 棧的特點和相關概念 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 散列函數(shù) 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 數(shù)組去重 146
4.4.2 求只出現(xiàn)一次的數(shù)字 147
4.4.3 兩數(shù)之和 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 獲得樹的結點數(shù) 160
5.2.5 獲得樹的高度 161
5.2.6 樹的深度優(yōu)先遍歷 161
5.2.7 深度優(yōu)先遍歷的遞歸實現(xiàn) 163
5.2.8 深度優(yōu)先遍歷的非遞歸實現(xiàn) 167
5.2.9 深度優(yōu)先遍歷的非遞歸實現(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 前驅結點與后繼結點 188
5.3.3 BST 的移除操作 190
5.4 總結 192
第 6 章堆與優(yōu)先隊列 194
6.1 二叉堆 194
6.2 堆排序 196
6.3 topK 問題 203
6.4 優(yōu)先隊列 205
6.5 丑數(shù) 208
6.6 小結 210
第 7 章 并查集 210
7.1 沒有優(yōu)化的并查集 210
7.2 快速合并，慢查找 214
7.3 基于重量的快速合并，快速查找 218
7.4 基于深度的快速合并，快速查找 220
7.5 基于深度與路徑壓縮的快速合并，快速查找 223
7.6 相關問題 226
7.6.1 朋友圈 226
7.6.2 島嶼的數(shù)量 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 區(qū)間查詢 242
8.1.5 區(qū)間修改 243
8.1.6 延遲標記 244
8.2 ZKW 線段樹 247
8.2.1 構建 247
8.2.2 單點查詢 248
8.2.3 單點修改 249
8.2.4 區(qū)間查詢 249
8.3 標記永久化技巧 251
8.3.1 基于標記永久化的區(qū)間修改 251
8.3.2 基于標記永久化的區(qū)間查詢 252
8.4 差分思想 253
8.4.1 基于差分思想的區(qū)間修改 254
8.4.2 基于差分思想的區(qū)間查詢 255
8.5 總結 255
第 9 章 樹狀數(shù)組 256
9.1 原理 256
9.2 構建 262
9.3 單點查詢 263
9.4 單點修改 264
9.5 求前 n 項之和 265
9.6 求 a~b 項之和 266
9.7 區(qū)間更新 266
9.8 區(qū)間最值 266
9.9 求逆序數(shù) 269
9.10 數(shù)組離散化 269
9.11 總結 273
第 10 章 前綴樹 274
10.1 原理 274
10.2 插入字符串 275
10.3 移除字符串 277
10.4 是否包含某個字符串 277
10.5 是否包含某個前綴 278
10.6 統(tǒng)計某個字符串出現(xiàn)的次數(shù) 278
10.7 統(tǒng)計某個前綴出現(xiàn)的次數(shù) 279
10.8 優(yōu)化 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 得到排序數(shù)組 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 根據排名找對應的數(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 根據排名找對應的數(shù) 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 區(qū)間刪除 326
12.3.6 獲取 value 的排名 327
12.3.7 根據排名找對應的數(shù) 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 素數(shù)環(huán) 409
14.3.3 批作業(yè)調度問題 411
14.3.4 八皇后問題 413
14.4 總結 415
第 15 章 動態(tài)規(guī)劃 416
15.1 斐波那契數(shù)列 416
15.1.1 暴力法 417
15.1.2 記憶化搜索 417
15.1.3 動態(tài)規(guī)劃法 418
15.2 找零錢 419
15.3 最長不下降子序列 421
15.4 最長公共子序列 423
15.5 爬樓梯 426
15.6 背包問題 427
15.7 總結 428
鄂公網安備 42010302001612號 