數據結構與算法之美 (全彩印刷)

王爭，前Google工程師，微信公眾號【小爭哥】作者，GitHub上算法教程Star數排名前列。
熱衷分享，致力於通俗易懂地講解數據結構和算法，幫助廣大程序員攻克算法學習、算法刷題、算法面試三項難關。

第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.1 C/C++中數組的實現方式19
2.2.2 Java中數組的實現方式20
2.2.3 JavaScript中數組的實現方式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.4 O(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.5 O(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.2 O(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.1 LRU緩存淘汰算法102
4.3.2 Java 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.5 B+樹：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.1 BF算法：編程語言中的查找、替換函數是怎樣實現的180
8.1.1 BF算法的原理與實現180
8.1.2 BF算法的性能分析181
8.1.3解答本節開篇問題181
8.1.4內容小結182
8.1.5思考題182
8.2 RK算法：如何借助哈希算法實現高效的字符串匹配182
8.2.1 RK算法的原理與實現182
8.2.2 RK算法的性能分析183
8.2.3內容小結184
8.2. 4思考題184
8.3 BM算法：如何實現文本編輯器中的查找和替換功能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.4 KMP算法：如何借助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.5 Trie樹：如何實現搜索引擎的搜索關鍵詞提示功能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.6 AC自動機：如何用多模式串匹配實現敏感詞過濾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