第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
· · · · · · (收起)