目錄
第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)排序:如何借助快速排序思想快速查找素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 LinkedHashMap104
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 K152
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.1BF算法的原理與實現180
8.1.2BF算法的性能分析181
8.1.3解答本節開篇問題181
8.1.4內容小結182
8.1.5思考題182
8.2RK算法:如何借助哈希算法實現高效的字符串匹配182
8.2.1RK算法的原理與實現182
8.2.2RK算法的性能分析183
8.2.3內容小結184
8.2.4思考題184
8.3BM算法:如何實現文本編輯器中的查找和替換功能185
8.3.1BM算法的核心思想185
8.3.2BM算法的原理分析186
8.3.3BM算法的代碼實現188
8.3.4BM算法的性能分析192
8.3.5解答本節開篇問題193
8.3.6內容小結193
8.3.7思考題193
8.4KMP算法:如何借助BM算法理解KMP算法194
8.4.1KMP算法的基本原理194
8.4.2失效函數的計算方法196
8.4.3KMP算法的性能分析197
8.4.4內容小結198
8.4.5思考題198
8.5Trie樹:如何實現搜索引擎的搜索關鍵詞提示功能198
8.5.1Trie樹的定義199
8.5.2Trie樹的代碼實現200
8.5.3Trie樹的性能分析201
8.5.4Trie樹與哈希表、紅黑樹的比較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.4AC自動機的性能分析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.2Dijkstra算法的原理與實現225
9.4.3Dijkstra算法的性能分析228
9.4.4Dijkstra算法思想的應用228
9.4.5解答本節開篇問題229
9.4.6內容小結230
9.4.7思考題230
9.5多源短路徑:如何利用Floyd算法解決傳遞閉包問題231
9.5.1Floyd算法的原理與實現231
9.5.2Floyd算法的性能分析232
9.5.3利用Floyd算法求解傳遞閉包232
9.5.4內容小結233
9.5.5思考題233
9.6啟發式搜索:如何用A*算法實現遊戲中的尋路功能233
9.6.1什麼是次優路線234
9.6.2A*算法的原理與實現234
9.6.3A*算法與Dijkstra算法的對比236
9.6.4解答本節開篇問題237
9.6.5內容小結237
9.6.6思考題238
9.7小生成樹:如何隨機生成遊戲中的迷宮地圖238
9.7.1什麼是小生成樹238
9.7.2Kruskal算法的原理與實現239
9.7.3Prim算法的原理與實現240
9.7.4解答本節開篇問題242
9.7.5內容小結244
9.7.6思考題245
9.8流:如何解決單身交友聯誼中的多匹配問題245
9.8.1什麼是流245
9.8.2Ford-Fulkerson方法246
9.8.3Edmonds-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.30-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.30-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.44種算法思想的比較分析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.1Redis數據庫介紹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