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

王爭(@小爭哥)

  • 數據結構與算法之美(全彩印刷)-preview-1
  • 數據結構與算法之美(全彩印刷)-preview-2
數據結構與算法之美(全彩印刷)-preview-1

買這商品的人也買了...

相關主題

商品描述

內 容 提 要

本書結合實際應用場景講解數據結構和算法,涵蓋常用、常考的數據結構和算法的原理講解、代碼實現和應用場景等。

本書分為11章。第1章介紹復雜度分析方法。第2章介紹數組、鏈表、棧和隊列這些基礎的線性表數據結構。第3章介紹遞歸編程技巧、8種經典排序、二分查找及二分查找的變體問題。第4章介紹哈希表、位圖、哈希算法和布隆過濾器。第5章介紹樹相關的數據結構,包括二叉樹、二叉查找樹、平衡二叉查找樹、遞歸樹和B+樹。第6章介紹堆,以及堆的各種應用,包括堆排序、優先級隊列、求Top K、求中位數和求百分位數。第7章介紹跳錶、並查集、線段樹和樹狀數組這些比較高級的數據結構。第8章介紹字符串匹配算法,包括BF算法、RK算法、BM算法、KMP算法、Trie樹和AC自動機。第9章介紹圖及相關算法,包括深度優先搜索、廣度優先搜索、拓撲排序、Dijkstra算法、Floyd算法、A*算法、最小生成樹算法、最大流算法和最大二分匹配等。第10章介紹4種算法思想,包括貪心、分治、回溯和動態規劃。第11章介紹4個經典項目中的數據結構和算法的應用,包括Redis、搜索引擎、鑒權限流和短網址服務。另外,附錄A為書中的思考題的解答。

盡管本書的大部分代碼採用Java語言編寫,但本書講解的知識與具體編程語言無關,因此,本書不但適合各種類型的研發工程師,而且可以作為高校電腦相關專業師生的學慣用書和培訓學校的教材。

作者簡介

王爭,前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