第1章復雜度分析 1
1.1復雜度分析（上）：如何分析代碼的執行效率和資源消耗 2
1.1.1復雜度分析的意義 2
1.1.2大O復雜度錶示法 2
1.1.3時間復雜度分析方法 4
1.1.4幾種常見的時間復雜度量級 5
1.1.5空間復雜度分析方法 7
1.1.6內容小結 7
1.1.7思考題 8
1.2復雜度分析（下）：詳解最好、最壞、平均、均攤這4種時間復雜度 8
1.2.1最好時間復雜度和最壞時間復雜度 8
1.2.2平均時間復雜度 9
1.2.3均攤時間復雜度 10
1.2.4內容小結 11
1.2.5思考題 12
第2章數組、鏈錶、棧和隊列 13
2.1數組（上）：為什麼數組的下標一般從0開始編號 14
2.1.1數組的定義 14
2.1.2尋址公式和隨機訪問特性 15
2.1.3低效的插入和刪除操作 15
2.1.4警惕數組訪問越界問題 16
2.1.5容器能否完全替代數組 17
2.1.6解答本節開篇問題 18
2.1.7內容小結 18
2.1.8思考題 18
2.2數組（下）：數據結構中的數組和編程語言中的數組的區彆 19
2.2.1C/C++中數組的實現方式 19
2.2.2Java中數組的實現方式 20
2.2.3JavaScript中數組的實現方式 22
2.2.4內容小結 23
2.2.5思考題 23
2.3鏈錶（上）：如何基於鏈錶實現LRU緩存淘汰算法 23
2.3.1鏈錶的底層存儲結構 24
2.3.2鏈錶的定義和操作 24
2.3.3鏈錶的變形結構 26
2.3.4鏈錶與數組的性能對比 28
2.3.5解答本節開篇問題 29
2.3.6內容小結 29
2.3.7思考題 30
2.4鏈錶（下）：藉助哪些技巧可以輕鬆地編寫鏈錶相關的復雜代碼 30
2.4.1技巧1：理解指針或引用的含義 30
2.4.2技巧2：警惕指針丟失和內存泄露 30
2.4.3技巧3：利用“哨兵”簡化代碼 31
2.4.4技巧4：留意邊界條件和特殊情況 33
2.4.5技巧5：舉例畫圖，輔助思考 34
2.4.6技巧6：多寫多練，沒有捷徑 34
2.4.7內容小結 34
2.4.8思考題 35
2.5棧：如何實現瀏覽器的前進和後退功能 35
2.5.1棧的定義 35
2.5.2順序棧和鏈式棧 35
2.5.3支持動態擴容的順序棧 36
2.5.4棧在函數調用中的應用 37
2.5.5棧在錶達式求值中的應用 38
2.5.6棧在括號匹配中的應用 38
2.5.7解答本節開篇問題 39
2.5.8內容小結 40
2.5.9思考題 40
2.6隊列：如何實現綫程池等有限資源池的請求排隊功能 40
2.6.1隊列的定義 40
2.6.2順序隊列和鏈式隊列 41
2.6.3循環隊列 42
2.6.4阻塞隊列和並發隊列 44
2.6.5解答本節開篇問題 44
2.6.6內容小結 45
2.6.7思考題 45
第3章遞歸、排序、二分查找 46
3.1遞歸：如何用3行代碼找到“最終推薦人” 47
3.1.1什麼是遞歸 47
3.1.2遞歸需要滿足的3個條件 48
3.1.3如何編寫遞歸代碼 48
3.1.4編寫遞歸代碼的難點 49
3.1.5警惕遞歸代碼齣現堆棧溢齣 49
3.1.6警惕遞歸代碼的重復計算問題 50
3.1.7將遞歸代碼改寫為非遞歸代碼 51
3.1.8解答本節開篇問題 52
3.1.9內容小結 52
3.1.10思考題 52
3.2尾遞歸：如何藉助尾遞歸避免遞歸過深導緻的堆棧溢齣 53
3.2.1遞歸産生堆棧溢齣的原因 53
3.2.2什麼樣的遞歸代碼可以改寫為尾遞歸 54
3.2.3尾遞歸真的可以避免堆棧溢齣嗎 54
3.2.4思考題 55
3.3排序算法基礎：從哪幾個方麵分析排序算法 55
3.3.1排序算法的執行效率 55
3.3.2排序算法的內存消耗 56
3.3.3排序算法的穩定性 56
3.3.4內容小結 57
3.3.5思考題 57
3.4O(n2)排序：為什麼插入排序比冒泡排序更受歡迎 58
3.4.1冒泡排序 58
3.4.2插入排序 60
3.4.3選擇排序 62
3.4.4解答本節開篇問題 63
3.4.5內容小結 64
3.4.6思考題 64
3.5O(nlogn)排序：如何藉助快速排序思想快速查找第K大元素 64
3.5.1歸並排序的原理和實現 64
3.5.2歸並排序的性能分析 66
3.5.3快速排序的原理和實現 68
3.5.4快速排序的性能分析 70
3.5.5解答本節開篇問題 71
3.5.6內容小結 72
3.5.7思考題 72
3.6綫性排序：如何根據年齡給100萬個用戶排序 72
3.6.1桶排序 73
3.6.2計數排序 74
3.6.3基數排序 76
3.6.4解答本節開篇問題 77
3.6.5內容小結 77
3.6.6思考題 77
3.7排序優化：如何實現一個高性能的通用的排序函數 78
3.7.1如何選擇閤適的排序算法 78
3.7.2如何優化快速排序 79
3.7.3排序函數舉例分析 79
3.7.4內容小結 80
3.7.5思考題 80
3.8二分查找：如何用最省內存的方式實現快速查找功能 80
3.8.1無處不在的二分思想 81
3.8.2O(logn)驚人的查找速度 82
3.8.3二分查找的遞歸與非遞歸實現 82
3.8.4二分查找應用場景的局限性 83
3.8.5解答本節開篇問題 84
3.8.6內容小結 85
3.8.7思考題 85
3.9二分查找的變體：如何快速定位IP地址對應的歸屬地 85
3.9.1什麼是二分查找變體問題 86
3.9.2變體問題1：查找第一個值等於給定值的元素 86
3.9.3變體問題2：查找最後一個值等於給定值的元素 88
3.9.4變體問題3：查找第一個值大於或等於給定值的元素 88
3.9.5變體問題4：查找最後一個值小於或等於給定值的元素 89
3.9.6解答本節開篇問題 89
3.9.7內容小結 90
3.9.8思考題 90
第4章哈希錶、位圖和哈希算法 91
4.1哈希錶（上）：Word軟件的單詞拼寫檢查功能是如何實現的 92
4.1.1哈希思想 92
4.1.2哈希函數 93
4.1.3哈希衝突 93
4.1.4解答本節開篇問題 95
4.1.5內容小結 95
4.1.6思考題 96
4.2哈希錶（中）：如何打造一個工業級的哈希錶 96
4.2.1設計哈希函數 96
4.2.2解決裝載因子過大的問題 97
4.2.3避免低效的擴容 98
4.2.4選擇閤適的衝突解決方法 99
4.2.5工業級的哈希錶舉例分析 100
4.2.6解答本節開篇問題 100
4.2.7內容小結 101
4.2.8思考題 101
4.3哈希錶（下）：如何利用哈希錶優化LRU緩存淘汰算法 101
4.3.1LRU緩存淘汰算法 102
4.3.2Java LinkedHashMap 104
4.3.3內容小結 105
4.3.4思考題 105
4.4位圖：如何實現網頁“爬蟲”中的網址鏈接去重功能 106
4.4.1基於哈希錶的解決方案 106
4.4.2基於位圖的解決方案 106
4.4.3基於布隆過濾器的解決方案 108
4.4.4迴答本節開篇問題 110
4.4.5內容小結 110
4.4.6思考題 111
4.5哈希算法：如何防止數據庫脫庫後用戶信息泄露 111
4.5.1哈希算法介紹 111
4.5.2應用1：安全加密 112
4.5.3應用2：唯一標識 113
4.5.4應用3：數據校驗 113
4.5.5應用4：哈希函數 113
4.5.6應用5：負載均衡 114
4.5.7應用6：數據分片 114
4.5.8應用7：分布式存儲 115
4.5.9解答本節開篇問題 116
4.5.10內容小結 116
4.5.11思考題 116
第5章樹 117
5.1樹和二叉樹：什麼樣的二叉樹適閤用數組存儲 118
5.1.1樹的定義 118
5.1.2二叉樹的定義 118
5.1.3二叉樹的存儲 119
5.1.4二叉樹的遍曆 120
5.1.5解答本節開篇問題 122
5.1.6內容小結 122
5.1.7思考題 122
5.2二叉查找樹：相比哈希錶，二叉查找樹有何優勢 122
5.2.1二叉查找樹的定義和操作 123
5.2.2支持重復數據的二叉查找樹 126
5.2.3二叉查找樹的性能分析 126
5.2.4解答本節開篇問題 127
5.2.5內容小結 128
5.2.6思考題 128
5.3平衡二叉查找樹：為什麼紅黑樹如此受歡迎 128
5.3.1平衡二叉查找樹的定義 128
5.3.2紅黑樹的定義 129
5.3.3紅黑樹的性能分析 129
5.3.4解答本節開篇問題 130
5.3.5內容小結 130
5.3.6思考題 131
5.4遞歸樹：如何藉助樹求遞歸算法的時間復雜度 131
5.4.1遞歸樹時間復雜度分析法 131
5.4.2實戰1：快速排序的時間復雜度分析 132
5.4.3實戰2：斐波那契數列的時間復雜度分析 133
5.4.4實戰3：全排列的時間復雜度分析 133
5.4.5內容小結 135
5.4.6思考題 135
5.5B+樹：MySQL數據庫索引是如何實現的 135
5.5.1典型需求：按值查詢和按區間查詢 135
5.5.2基於哈希錶和二叉查找樹的解決方案 136
5.5.3基於B+樹的解決方案 136
5.5.4內容小結 139
5.5.5思考題 140
第6章堆 141
6.1堆：如何維護動態集閤的最值 142
6.1.1堆的定義 142
6.1.2堆的存儲 142
6.1.3往堆中插入元素 143
6.1.4刪除堆頂元素 144
6.1.5刪除任意元素 145
6.1.6堆的性能分析 145
6.1.7解答本節開篇問題 145
6.1.8內容小結 146
6.1.9思考題 146
6.2堆排序：為什麼說堆排序沒有快速排序快 147
6.2.1堆排序之建堆 147
6.2.2堆排序之排序 149
6.2.3堆排序的性能分析 149
6.2.4解答本節開篇問題 150
6.2.5內容小結 150
6.2.6思考題 151
6.3堆的應用：如何快速獲取Top 10熱門搜索關鍵詞 151
6.3.1堆的應用1：優先級隊列 151
6.3.2堆的應用2：求Top K 152
6.3.3堆的應用3：求中位數和百分位數 153
6.3.4解答本節開篇問題 155
6.3.5內容小結 155
6.3.6思考題 156
第7章跳錶、並查集、綫段樹和樹狀數組 157
7.1跳錶：Redis中的有序集閤類型是如何實現的 158
7.1.1 跳錶的由來 158
7.1.2 用跳錶查詢到底有多快 159
7.1.3 跳錶是不是很浪費內存 160
7.1.4 高效插入和刪除 161
7.1.5 跳錶索引動態更新 162
7.1.6 解答本節開篇問題 162
7.1.7 內容小結 163
7.1.8 思考題 163
7.2並查集：路徑壓縮和按秩閤並這兩個優化是否衝突 163
7.2.1 並查集的由來 163
7.2.2 基於鏈錶的實現思路 164
7.2.3 基於樹的實現思路 166
7.2.4 內容小結 168
7.2.5 思考題 168
7.3綫段樹：如何查找獵聘網中積分排在第K位的獵頭 168
7.3.1 區間統計問題 169
7.3.2 綫段樹的其他應用 172
7.3.3 解答本節開篇問題 174
7.3.4 內容小結 174
7.3.5 思考題 174
7.4樹狀數組：如何實現一個高性能、低延遲的實時排行榜 174
7.4.1 “前綴和”問題 175
7.4.2 樹狀數組與綫段樹的對比 177
7.4.3 解答本節開篇問題 177
7.4.4 內容小結 178
7.4.5 思考題 178
第8章字符串匹配算法 179
8.1BF算法：編程語言中的查找、替換函數是怎樣實現的 180
8.1.1 BF算法的原理與實現 180
8.1.2 BF算法的性能分析 181
8.1.3 解答本節開篇問題 181
8.1.4 內容小結 182
8.1.5 思考題 182
8.2RK算法：如何藉助哈希算法實現高效的字符串匹配 182
8.2.1 RK算法的原理與實現 182
8.2.2 RK算法的性能分析 183
8.2.3 內容小結 184
8.2.4 思考題 184
8.3BM算法：如何實現文本編輯器中的查找和替換功能 185
8.3.1 BM算法的核心思想 185
8.3.2 BM算法的原理分析 186
8.3.3 BM算法的代碼實現 188
8.3.4 BM算法的性能分析 192
8.3.5 解答本節開篇問題 193
8.3.6 內容小結 193
8.3.7 思考題 193
8.4KMP算法：如何藉助BM算法理解KMP算法 194
8.4.1 KMP算法的基本原理 194
8.4.2 失效函數的計算方法 196
8.4.3 KMP算法的性能分析 197
8.4.4 內容小結 198
8.4.5 思考題 198
8.5Trie樹：如何實現搜索引擎的搜索關鍵詞提示功能 198
8.5.1 Trie樹的定義 199
8.5.2 Trie樹的代碼實現 200
8.5.3 Trie樹的性能分析 201
8.5.4 Trie樹與哈希錶、紅黑樹的比較 202
8.5.5 解答本節開篇問題 202
8.5.6 內容小結 203
8.5.7 思考題 204
8.6AC自動機：如何用多模式串匹配實現敏感詞過濾 204
8.6.1 基於單模式串的敏感詞過濾 204
8.6.2 基於Trie樹的敏感詞過濾 205
8.6.3 基於AC自動機的敏感詞過濾 205
8.6.4 AC自動機的性能分析 208
8.6.5 內容小結 209
8.6.6 思考題 209
第9章圖 210
9.1圖的錶示：如何存儲微博、微信等社交網絡中的好友關係 211
9.1.1 圖的定義 211
9.1.2 鄰接矩陣的存儲方法 212
9.1.3 鄰接錶的存儲方法 213
9.1.4 解答本節開篇問題 214
9.1.5 內容小結 215
9.1.6 思考題 215
9.2深度優先搜索和廣度優先搜索：如何找齣社交網絡中的三度好友關係 216
9.2.1 什麼是搜索算法 216
9.2.2 廣度優先搜索 217
9.2.3 深度優先搜索 219
9.2.4 解答本節開篇問題 220
9.2.5 內容小結 220
9.2.6 思考題 220
9.3拓撲排序：如何確定代碼源文件的編譯依賴關係 221
9.3.1 什麼是拓撲排序 221
9.3.2 利用Kahn算法實現拓撲排序 222
9.3.3 利用深度優先搜索實現拓撲排序 222
9.3.4 利用拓撲排序檢測環 223
9.3.5 解答本節開篇問題 224
9.3.6 內容小結 224
9.3.7 思考題 224
9.4單源最短路徑：地圖軟件如何“計算”最優齣行路綫 225
9.4.1 最短路徑算法介紹 225
9.4.2 Dijkstra算法的原理與實現 225
9.4.3 Dijkstra算法的性能分析 228
9.4.4 Dijkstra算法思想的應用 228
9.4.5 解答本節開篇問題 229
9.4.6 內容小結 230
9.4.7 思考題 230
9.5多源最短路徑：如何利用Floyd算法解決傳遞閉包問題 231
9.5.1 Floyd算法的原理與實現 231
9.5.2 Floyd算法的性能分析 232
9.5.3 利用Floyd算法求解傳遞閉包 232
9.5.4 內容小結 233
9.5.5 思考題 233
9.6啓發式搜索：如何用A*算法實現遊戲中的尋路功能 233
9.6.1 什麼是次優路綫 234
9.6.2 A*算法的原理與實現 234
9.6.3 A*算法與Dijkstra算法的對比 236
9.6.4 解答本節開篇問題 237
9.6.5 內容小結 237
9.6.6 思考題 238
9.7最小生成樹：如何隨機生成遊戲中的迷宮地圖 238
9.7.1 什麼是最小生成樹 238
9.7.2 Kruskal算法的原理與實現 239
9.7.3 Prim算法的原理與實現 240
9.7.4 解答本節開篇問題 242
9.7.5 內容小結 244
9.7.6 思考題 245
9.8最大流：如何解決單身交友聯誼中的最多匹配問題 245
9.8.1 什麼是最大流 245
9.8.2 Ford-Fulkerson方法 246
9.8.3 Edmonds-Karp算法 247
9.8.4 最大二分匹配 249
9.8.5 解答本節開篇問題 249
9.8.6 內容小結 249
9.8.7 思考題 250
第10章貪心、分治、迴溯和動態規劃 251
10.1貪心算法：如何利用貪心算法實現霍夫曼編碼 252
10.1.1 如何理解貪心算法 252
10.1.2 貪心算法的應用示例 253
10.1.3 解答本節開篇問題 255
10.1.4 內容小結 256
10.1.5 思考題 256
10.2分治算法：談一談大規模計算框架MapReduce中的分治思想 256
10.2.1 如何理解分治算法 257
10.2.2 分治算法的應用示例 257
10.2.3 分治算法在大數據處理中的應用 259
10.2.4 解答本節開篇問題 259
10.2.5 內容小結 260
10.2.6 思考題 260
10.3迴溯算法：從電影《蝴蝶效應》中學習迴溯算法的核心思想 260
10.3.1 如何理解迴溯算法 261
10.3.2 八皇後問題 261
10.3.3 0-1背包問題 262
10.3.4 正則錶達式匹配問題 263
10.3.5 內容小結 264
10.3.6 思考題 264
10.4初識動態規劃：如何巧妙解決“雙11”購物時的湊單問題 264
10.4.1 動態規劃的學習路綫 265
10.4.2 利用動態規劃解決0-1背包問題 265
10.4.3 0-1背包問題的升級版 269
10.4.4 解答本節開篇問題 270
10.4.5 內容小結 271
10.4.6 思考題 272
10.5動態規劃理論：徹底理解最優子結構、無後效性和重復子問題 272
10.5.1 “一個模型和三個特徵”理論介紹 272
10.5.2 “一個模型和三個特徵”的應用示例 273
10.5.3 動態規劃的兩種解題方法 274
10.5.4 4種算法思想的比較分析 277
10.5.5 內容小結 277
10.5.6 思考題 278
10.6動態規劃實戰：如何實現搜索引擎中的拼寫糾錯功能 278
10.6.1 如何量化兩個字符串的相似度 278
10.6.2 如何通過編程計算萊文斯坦距離 279
10.6.3 如何通過編程計算最長公共子串長度 281
10.6.4 解答本節開篇問題 282
10.6.5 內容小結 283
10.6.6 思考題 283
第11章數據結構和算法實戰 284
11.1實戰1：剖析Redis的常用數據類型對應的數據結構 285
11.1.1 Redis數據庫介紹 285
11.1.2 列錶（list） 285
11.1.3 哈希（hash） 286
11.1.4 集閤（set） 286
11.1.5 有序集閤（sorted set） 287
11.1.6 數據結構的持久化問題 287
11.1.7 總結和引申 288
11.1.8 思考題 288
11.2實戰2：剖析搜索引擎背後的經典數據結構和算法 288
11.2.1 搜索引擎係統的整體介紹 288
11.2.2 搜集 289
11.2.3 分析 290
11.2.4 索引 292
11.2.5 查詢 292
11.2.6 總結和引申 293
11.2.7 思考題 293
11.3實戰3：剖析微服務鑒權和限流背後的數據結構和算法 293
11.3.1 鑒權背景介紹 294
11.3.2 如何實現快速鑒權 294
11.3.3 限流背景介紹 297
11.3.4 如何實現精準限流 297
11.3.5 總結和引申 298
11.3.6 思考題 299
11.4實戰4：用學過的數據結構和算法實現短網址服務 299
11.4.1 短網址服務的整體介紹 299
11.4.2 通過哈希算法生成短網址 299
11.4.3 通過ID生成器生成短網址 302
11.4.4 總結和引申 303
11.4.5 思考題 303
附錄A思考題答案 304
· · · · · · (
收起)
