1.好評爆表的極客時間算法專欄網紅達人，GitHub上算法教程Star數量上萬的作者新作；2.10多萬人驗證過的、為求職面試者、工程師量身打造的數據結構與算法私教課；3.20個經典數據結構與算法，一冊在手，學習算法不愁，輕松搞定大廠的面試秘籍；4.100個真實項目場景案例，助力工程師解決項目中的實際算法難題；5.300多幅算法手繪圖解，文科生都能學的懂算法通關書；

●第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.2JavaLinkedHashMap104
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堆的應用：如何快速獲取Top10熱門搜索關鍵詞151
6.3.1堆的應用1：優先級隊列151
6.3.2堆的應用2：求TopK152
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有序集合(sortedset)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

本書結合實際應用場景講解數據結構和算法，涵蓋常用、常考的數據結構和算法的原理講解、代碼實現和應用場景等。
本書分為11章。第1章介紹復雜度分析方法。第2章介紹數組、鏈表、棧和隊列這些基礎的線性表數據結構。第3章介紹遞歸編程技巧、8種經典排序、二分查找及二分查找的變體問題。第4章介紹哈希表、位圖、哈希算法和布隆過濾器。第5章介紹樹相關的數據結構，包括二叉樹、二叉查找樹、平衡二叉查找樹、遞歸樹和B+樹。第6章介紹堆，以及堆的各種應用，包括堆排序、優先級隊列、求TopK、求中位數和求百分位數。第7章介紹跳表、並查集、線段樹和樹狀數組這些比較高級的數據結構。第8章介紹字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie樹和AC自動機。第9章介紹圖及相關算法，包括深度優先搜索、廣度優先搜索、拓撲排序、Dijkstra算法、Floyd算法、A*算法、最小生成樹算法、優選流等

王爭 著