數(shù)據(jù)結(jié)構(gòu)與算法之美（全彩印刷）
定 價(jià)：119.8 元
- 作者：王爭(zhēng)（@小爭(zhēng)哥）
- 出版時(shí)間：2021/6/1
- ISBN：9787115562050
- 出 版 社：人民郵電出版社
- 中圖法分類：TP311.12
- 頁碼：334
- 紙張：
- 版次：01
- 開本：16開
內(nèi) 容 提 要
本書結(jié)合實(shí)際應(yīng)用場(chǎng)景講解數(shù)據(jù)結(jié)構(gòu)和算法，涵蓋常用、�？嫉臄�(shù)據(jù)結(jié)構(gòu)和算法的原理講解、代碼實(shí)現(xiàn)和應(yīng)用場(chǎng)景等。
本書分為11章。第1章介紹復(fù)雜度分析方法。第2章介紹數(shù)組、鏈表、棧和隊(duì)列這些基礎(chǔ)的線性表數(shù)據(jù)結(jié)構(gòu)。第3章介紹遞歸編程技巧、8種經(jīng)典排序、二分查找及二分查找的變體問題。第4章介紹哈希表、位圖、哈希算法和布隆過濾器。第5章介紹樹相關(guān)的數(shù)據(jù)結(jié)構(gòu)，包括二叉樹、二叉查找樹、平衡二叉查找樹、遞歸樹和B+樹。第6章介紹堆，以及堆的各種應(yīng)用，包括堆排序、優(yōu)先級(jí)隊(duì)列、求Top K、求中位數(shù)和求百分位數(shù)。第7章介紹跳表、并查集、線段樹和樹狀數(shù)組這些比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)。第8章介紹字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie樹和AC自動(dòng)機(jī)。第9章介紹圖及相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、拓?fù)渑判�、Dijkstra算法、Floyd算法、A*算法、最小生成樹算法、最大流算法和最大二分匹配等。第10章介紹4種算法思想，包括貪心、分治、回溯和動(dòng)態(tài)規(guī)劃。第11章介紹4個(gè)經(jīng)典項(xiàng)目中的數(shù)據(jù)結(jié)構(gòu)和算法的應(yīng)用，包括Redis、搜索引擎、鑒權(quán)限流和短網(wǎng)址服務(wù)。另外，附錄A為書中的思考題的解答。
盡管本書的大部分代碼采用Java語言編寫，但本書講解的知識(shí)與具體編程語言無關(guān)，因此，本書不但適合各種類型的研發(fā)工程師，而且可以作為高校計(jì)算機(jī)相關(guān)專業(yè)師生的學(xué)習(xí)用書和培訓(xùn)學(xué)校的教材。
1.好評(píng)爆表的極客時(shí)間算法專欄網(wǎng)紅達(dá)人，GitHub上算法教程Star數(shù)量上萬的作者新作；
2.10多萬人驗(yàn)證過的、為求職面試者、工程師量身打造的數(shù)據(jù)結(jié)構(gòu)與算法私教課；
3.20個(gè)經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法，一冊(cè)在手，學(xué)習(xí)算法不愁，輕松搞定大廠的面試秘籍；
4.100個(gè)真實(shí)項(xiàng)目場(chǎng)景案例，助力工程師解決項(xiàng)目中的實(shí)際算法難題；
5.300多幅算法手繪圖解，文科生都能學(xué)的懂算法通關(guān)書；
王爭(zhēng)，前Google工程師，微信公眾號(hào)【小爭(zhēng)哥】作者，GitHub上算法教程Star數(shù)排名前列。熱衷分享，致力于通俗易懂地講解數(shù)據(jù)結(jié)構(gòu)和算法，幫助廣大程序員攻克算法學(xué)習(xí)、算法刷題、算法面試三項(xiàng)難關(guān)。
目錄
第1章 復(fù)雜度分析 1
1.1 復(fù)雜度分析（上）：如何分析代碼的執(zhí)行效率和資源消耗 2
1.1.1 復(fù)雜度分析的意義 2
1.1.2 大O復(fù)雜度表示法 2
1.1.3 時(shí)間復(fù)雜度分析方法 4
1.1.4 幾種常見的時(shí)間復(fù)雜度量級(jí) 5
1.1.5 空間復(fù)雜度分析方法 7
1.1.6 內(nèi)容小結(jié) 7
1.1.7 思考題 8
1.2 復(fù)雜度分析（下）：詳解最好、最壞、平均、均攤這4種時(shí)間復(fù)雜度 8
1.2.1 最好時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度 8
1.2.2 平均時(shí)間復(fù)雜度 9
1.2.3 均攤時(shí)間復(fù)雜度 10
1.2.4 內(nèi)容小結(jié) 11
1.2.5 思考題 12
第2章 數(shù)組、鏈表、棧和隊(duì)列 13
2.1 數(shù)組（上）：為什么數(shù)組的下標(biāo)一般從0開始編號(hào) 14
2.1.1 數(shù)組的定義 14
2.1.2 尋址公式和隨機(jī)訪問特性 15
2.1.3 低效的插入和刪除操作 15
2.1.4 警惕數(shù)組訪問越界問題 16
2.1.5 容器能否完全替代數(shù)組 17
2.1.6 解答本節(jié)開篇問題 18
2.1.7 內(nèi)容小結(jié) 18
2.1.8 思考題 18
2.2 數(shù)組（下）：數(shù)據(jù)結(jié)構(gòu)中的數(shù)組和編程語言中的數(shù)組的區(qū)別 19
2.2.1 C/C++中數(shù)組的實(shí)現(xiàn)方式 19
2.2.2 Java中數(shù)組的實(shí)現(xiàn)方式 20
2.2.3 JavaScript中數(shù)組的實(shí)現(xiàn)方式 22
2.2.4 內(nèi)容小結(jié) 23
2.2.5 思考題 23
2.3 鏈表（上）：如何基于鏈表實(shí)現(xiàn)LRU緩存淘汰算法 23
2.3.1 鏈表的底層存儲(chǔ)結(jié)構(gòu) 24
2.3.2 鏈表的定義和操作 24
2.3.3 鏈表的變形結(jié)構(gòu) 26
2.3.4 鏈表與數(shù)組的性能對(duì)比 28
2.3.5 解答本節(jié)開篇問題 29
2.3.6 內(nèi)容小結(jié) 29
2.3.7 思考題 30
2.4 鏈表（下）：借助哪些技巧可以輕松地編寫鏈表相關(guān)的復(fù)雜代碼 30
2.4.1 技巧1：理解指針或引用的含義 30
2.4.2 技巧2：警惕指針丟失和內(nèi)存泄露 30
2.4.3 技巧3：利用“哨兵”簡(jiǎn)化代碼 31
2.4.4 技巧4：留意邊界條件和特殊情況 33
2.4.5 技巧5：舉例畫圖，輔助思考 34
2.4.6 技巧6：多寫多練，沒有捷徑 34
2.4.7 內(nèi)容小結(jié) 34
2.4.8 思考題 35
2.5 棧：如何實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能 35
2.5.1 棧的定義 35
2.5.2 順序棧和鏈?zhǔn)綏！?5
2.5.3 支持動(dòng)態(tài)擴(kuò)容的順序棧 36
2.5.4 棧在函數(shù)調(diào)用中的應(yīng)用 37
2.5.5 棧在表達(dá)式求值中的應(yīng)用 38
2.5.6 棧在括號(hào)匹配中的應(yīng)用 38
2.5.7 解答本節(jié)開篇問題 39
2.5.8 內(nèi)容小結(jié) 40
2.5.9 思考題 40
2.6 隊(duì)列：如何實(shí)現(xiàn)線程池等有限資源池的請(qǐng)求排隊(duì)功能 40
2.6.1 隊(duì)列的定義 40
2.6.2 順序隊(duì)列和鏈?zhǔn)疥?duì)列 41
2.6.3 循環(huán)隊(duì)列 42
2.6.4 阻塞隊(duì)列和并發(fā)隊(duì)列 44
2.6.5 解答本節(jié)開篇問題 44
2.6.6 內(nèi)容小結(jié) 45
2.6.7 思考題 45
第3章 遞歸、排序、二分查找 46
3.1 遞歸：如何用3行代碼找到“最終推薦人” 47
3.1.1 什么是遞歸 47
3.1.2 遞歸需要滿足的3個(gè)條件 48
3.1.3 如何編寫遞歸代碼 48
3.1.4 編寫遞歸代碼的難點(diǎn) 49
3.1.5 警惕遞歸代碼出現(xiàn)堆棧溢出 49
3.1.6 警惕遞歸代碼的重復(fù)計(jì)算問題 50
3.1.7 將遞歸代碼改寫為非遞歸代碼 51
3.1.8 解答本節(jié)開篇問題 52
3.1.9 內(nèi)容小結(jié) 52
3.1.10 思考題 52
3.2 尾遞歸：如何借助尾遞歸避免遞歸過深導(dǎo)致的堆棧溢出 53
3.2.1 遞歸產(chǎn)生堆棧溢出的原因 53
3.2.2 什么樣的遞歸代碼可以改寫為尾遞歸 54
3.2.3 尾遞歸真的可以避免堆棧溢出嗎 54
3.2.4 思考題 55
3.3 排序算法基礎(chǔ)：從哪幾個(gè)方面分析排序算法 55
3.3.1 排序算法的執(zhí)行效率 55
3.3.2 排序算法的內(nèi)存消耗 56
3.3.3 排序算法的穩(wěn)定性 56
3.3.4 內(nèi)容小結(jié) 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 解答本節(jié)開篇問題 63
3.4.5 內(nèi)容小結(jié) 64
3.4.6 思考題 64
3.5 O(nlogn)排序：如何借助快速排序思想快速查找第K大元素 64
3.5.1 歸并排序的原理和實(shí)現(xiàn) 64
3.5.2 歸并排序的性能分析 66
3.5.3 快速排序的原理和實(shí)現(xiàn) 68
3.5.4 快速排序的性能分析 70
3.5.5 解答本節(jié)開篇問題 71
3.5.6 內(nèi)容小結(jié) 72
3.5.7 思考題 72
3.6 線性排序：如何根據(jù)年齡給100萬個(gè)用戶排序 72
3.6.1 桶排序 73
3.6.2 計(jì)數(shù)排序 74
3.6.3 基數(shù)排序 76
3.6.4 解答本節(jié)開篇問題 77
3.6.5 內(nèi)容小結(jié) 77
3.6.6 思考題 77
3.7 排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)高性能的通用的排序函數(shù) 78
3.7.1 如何選擇合適的排序算法 78
3.7.2 如何優(yōu)化快速排序 79
3.7.3 排序函數(shù)舉例分析 79
3.7.4 內(nèi)容小結(jié) 80
3.7.5 思考題 80
3.8 二分查找：如何用最省內(nèi)存的方式實(shí)現(xiàn)快速查找功能 80
3.8.1 無處不在的二分思想 81
3.8.2 O(logn)驚人的查找速度 82
3.8.3 二分查找的遞歸與非遞歸實(shí)現(xiàn) 82
3.8.4 二分查找應(yīng)用場(chǎng)景的局限性 83
3.8.5 解答本節(jié)開篇問題 84
3.8.6 內(nèi)容小結(jié) 85
3.8.7 思考題 85
3.9 二分查找的變體：如何快速定位IP地址對(duì)應(yīng)的歸屬地 85
3.9.1 什么是二分查找變體問題 86
3.9.2 變體問題1：查找第一個(gè)值等于給定值的元素 86
3.9.3 變體問題2：查找最后一個(gè)值等于給定值的元素 88
3.9.4 變體問題3：查找第一個(gè)值大于或等于給定值的元素 88
3.9.5 變體問題4：查找最后一個(gè)值小于或等于給定值的元素 89
3.9.6 解答本節(jié)開篇問題 89
3.9.7 內(nèi)容小結(jié) 90
3.9.8 思考題 90
第4章 哈希表、位圖和哈希算法 91
4.1 哈希表（上）：Word軟件的單詞拼寫檢查功能是如何實(shí)現(xiàn)的 92
4.1.1 哈希思想 92
4.1.2 哈希函數(shù) 93
4.1.3 哈希沖突 93
4.1.4 解答本節(jié)開篇問題 95
4.1.5 內(nèi)容小結(jié) 95
4.1.6 思考題 96
4.2 哈希表（中）：如何打造一個(gè)工業(yè)級(jí)的哈希表 96
4.2.1 設(shè)計(jì)哈希函數(shù) 96
4.2.2 解決裝載因子過大的問題 97
4.2.3 避免低效的擴(kuò)容 98
4.2.4 選擇合適的沖突解決方法 99
4.2.5 工業(yè)級(jí)的哈希表舉例分析 100
4.2.6 解答本節(jié)開篇問題 100
4.2.7 內(nèi)容小結(jié) 101
4.2.8 思考題 101
4.3 哈希表（下）：如何利用哈希表優(yōu)化LRU緩存淘汰算法 101
4.3.1 LRU緩存淘汰算法 102
4.3.2 Java LinkedHashMap 104
4.3.3 內(nèi)容小結(jié) 105
4.3.4 思考題 105
4.4 位圖：如何實(shí)現(xiàn)網(wǎng)頁“爬蟲”中的網(wǎng)址鏈接去重功能 106
4.4.1 基于哈希表的解決方案 106
4.4.2 基于位圖的解決方案 106
4.4.3 基于布隆過濾器的解決方案 108
4.4.4 回答本節(jié)開篇問題 110
4.4.5 內(nèi)容小結(jié) 110
4.4.6 思考題 111
4.5 哈希算法：如何防止數(shù)據(jù)庫(kù)脫庫(kù)后用戶信息泄露 111
4.5.1 哈希算法介紹 111
4.5.2 應(yīng)用1：安全加密 112
4.5.3 應(yīng)用2：唯一標(biāo)識(shí) 113
4.5.4 應(yīng)用3：數(shù)據(jù)校驗(yàn) 113
4.5.5 應(yīng)用4：哈希函數(shù) 113
4.5.6 應(yīng)用5：負(fù)載均衡 114
4.5.7 應(yīng)用6：數(shù)據(jù)分片 114
4.5.8 應(yīng)用7：分布式存儲(chǔ) 115
4.5.9 解答本節(jié)開篇問題 116
4.5.10 內(nèi)容小結(jié) 116
4.5.11 思考題 116
第5章 樹 117
5.1 樹和二叉樹：什么樣的二叉樹適合用數(shù)組存儲(chǔ) 118
5.1.1 樹的定義 118
5.1.2 二叉樹的定義 118
5.1.3 二叉樹的存儲(chǔ) 119
5.1.4 二叉樹的遍歷 120
5.1.5 解答本節(jié)開篇問題 122
5.1.6 內(nèi)容小結(jié) 122
5.1.7 思考題 122
5.2 二叉查找樹：相比哈希表，二叉查找樹有何優(yōu)勢(shì) 122
5.2.1 二叉查找樹的定義和操作 123
5.2.2 支持重復(fù)數(shù)據(jù)的二叉查找樹 126
5.2.3 二叉查找樹的性能分析 126
5.2.4 解答本節(jié)開篇問題 127
5.2.5 內(nèi)容小結(jié) 128
5.2.6 思考題 128
5.3 平衡二叉查找樹：為什么紅黑樹如此受歡迎 128
5.3.1 平衡二叉查找樹的定義 128
5.3.2 紅黑樹的定義 129
5.3.3 紅黑樹的性能分析 129
5.3.4 解答本節(jié)開篇問題 130
5.3.5 內(nèi)容小結(jié) 130
5.3.6 思考題 131
5.4 遞歸樹：如何借助樹求遞歸算法的時(shí)間復(fù)雜度 131
5.4.1 遞歸樹時(shí)間復(fù)雜度分析法 131
5.4.2 實(shí)戰(zhàn)1：快速排序的時(shí)間復(fù)雜度分析 132
5.4.3 實(shí)戰(zhàn)2：斐波那契數(shù)列的時(shí)間復(fù)雜度分析 133
5.4.4 實(shí)戰(zhàn)3：全排列的時(shí)間復(fù)雜度分析 133
5.4.5 內(nèi)容小結(jié) 135
5.4.6 思考題 135
5.5 B+樹：MySQL數(shù)據(jù)庫(kù)索引是如何實(shí)現(xiàn)的 135
5.5.1 典型需求：按值查詢和按區(qū)間查詢 135
5.5.2 基于哈希表和二叉查找樹的解決方案 136
5.5.3 基于B+樹的解決方案 136
5.5.4 內(nèi)容小結(jié) 139
5.5.5 思考題 140
第6章 堆 141
6.1 堆：如何維護(hù)動(dòng)態(tài)集合的最值 142
6.1.1 堆的定義 142
6.1.2 堆的存儲(chǔ) 142
6.1.3 往堆中插入元素 143
6.1.4 刪除堆頂元素 144
6.1.5 刪除任意元素 145
6.1.6 堆的性能分析 145
6.1.7 解答本節(jié)開篇問題 145
6.1.8 內(nèi)容小結(jié) 146
6.1.9 思考題 146
6.2 堆排序：為什么說堆排序沒有快速排序快 147
6.2.1 堆排序之建堆 147
6.2.2 堆排序之排序 149
6.2.3 堆排序的性能分析 149
6.2.4 解答本節(jié)開篇問題 150
6.2.5 內(nèi)容小結(jié) 150
6.2.6 思考題 151
6.3 堆的應(yīng)用：如何快速獲取Top 10熱門搜索關(guān)鍵詞 151
6.3.1 堆的應(yīng)用1：優(yōu)先級(jí)隊(duì)列 151
6.3.2 堆的應(yīng)用2：求Top K 152
6.3.3 堆的應(yīng)用3：求中位數(shù)和百分位數(shù) 153
6.3.4 解答本節(jié)開篇問題 155
6.3.5 內(nèi)容小結(jié) 155
6.3.6 思考題 156
第7章 跳表、并查集、線段樹和樹狀數(shù)組 157
7.1 跳表：Redis中的有序集合類型是如何實(shí)現(xiàn)的 158
7.1.1 跳表的由來 158
7.1.2 用跳表查詢到底有多快 159
7.1.3 跳表是不是很浪費(fèi)內(nèi)存 160
7.1.4 高效插入和刪除 161
7.1.5 跳表索引動(dòng)態(tài)更新 162
7.1.6 解答本節(jié)開篇問題 162
7.1.7 內(nèi)容小結(jié) 163
7.1.8 思考題 163
7.2 并查集：路徑壓縮和按秩合并這兩個(gè)優(yōu)化是否沖突 163
7.2.1 并查集的由來 163
7.2.2 基于鏈表的實(shí)現(xiàn)思路 164
7.2.3 基于樹的實(shí)現(xiàn)思路 166
7.2.4 內(nèi)容小結(jié) 168
7.2.5 思考題 168
7.3 線段樹：如何查找獵聘網(wǎng)中積分排在第K位的獵頭 168
7.3.1 區(qū)間統(tǒng)計(jì)問題 169
7.3.2 線段樹的其他應(yīng)用 172
7.3.3 解答本節(jié)開篇問題 174
7.3.4 內(nèi)容小結(jié) 174
7.3.5 思考題 174
7.4 樹狀數(shù)組：如何實(shí)現(xiàn)一個(gè)高性能、低延遲的實(shí)時(shí)排行榜 174
7.4.1 “前綴和”問題 175
7.4.2 樹狀數(shù)組與線段樹的對(duì)比 177
7.4.3 解答本節(jié)開篇問題 177
7.4.4 內(nèi)容小結(jié) 178
7.4.5 思考題 178
第8章 字符串匹配算法 179
8.1 BF算法：編程語言中的查找、替換函數(shù)是怎樣實(shí)現(xiàn)的 180
8.1.1 BF算法的原理與實(shí)現(xiàn) 180
8.1.2 BF算法的性能分析 181
8.1.3 解答本節(jié)開篇問題 181
8.1.4 內(nèi)容小結(jié) 182
8.1.5 思考題 182
8.2 RK算法：如何借助哈希算法實(shí)現(xiàn)高效的字符串匹配 182
8.2.1 RK算法的原理與實(shí)現(xiàn) 182
8.2.2 RK算法的性能分析 183
8.2.3 內(nèi)容小結(jié) 184
8.2.4 思考題 184
8.3 BM算法：如何實(shí)現(xiàn)文本編輯器中的查找和替換功能 185
8.3.1 BM算法的核心思想 185
8.3.2 BM算法的原理分析 186
8.3.3 BM算法的代碼實(shí)現(xiàn) 188
8.3.4 BM算法的性能分析 192
8.3.5 解答本節(jié)開篇問題 193
8.3.6 內(nèi)容小結(jié) 193
8.3.7 思考題 193
8.4 KMP算法：如何借助BM算法理解KMP算法 194
8.4.1 KMP算法的基本原理 194
8.4.2 失效函數(shù)的計(jì)算方法 196
8.4.3 KMP算法的性能分析 197
8.4.4 內(nèi)容小結(jié) 198
8.4.5 思考題 198
8.5 Trie樹：如何實(shí)現(xiàn)搜索引擎的搜索關(guān)鍵詞提示功能 198
8.5.1 Trie樹的定義 199
8.5.2 Trie樹的代碼實(shí)現(xiàn) 200
8.5.3 Trie樹的性能分析 201
8.5.4 Trie樹與哈希表、紅黑樹的比較 202
8.5.5 解答本節(jié)開篇問題 202
8.5.6 內(nèi)容小結(jié) 203
8.5.7 思考題 204
8.6 AC自動(dòng)機(jī)：如何用多模式串匹配實(shí)現(xiàn)敏感詞過濾 204
8.6.1 基于單模式串的敏感詞過濾 204
8.6.2 基于Trie樹的敏感詞過濾 205
8.6.3 基于AC自動(dòng)機(jī)的敏感詞過濾 205
8.6.4 AC自動(dòng)機(jī)的性能分析 208
8.6.5 內(nèi)容小結(jié) 209
8.6.6 思考題 209
第9章 圖 210
9.1 圖的表示：如何存儲(chǔ)微博、微信等社交網(wǎng)絡(luò)中的好友關(guān)系 211
9.1.1 圖的定義 211
9.1.2 鄰接矩陣的存儲(chǔ)方法 212
9.1.3 鄰接表的存儲(chǔ)方法 213
9.1.4 解答本節(jié)開篇問題 214
9.1.5 內(nèi)容小結(jié) 215
9.1.6 思考題 215
9.2 深度優(yōu)先搜索和廣度優(yōu)先搜索：如何找出社交網(wǎng)絡(luò)中的三度好友關(guān)系 216
9.2.1 什么是搜索算法 216
9.2.2 廣度優(yōu)先搜索 217
9.2.3 深度優(yōu)先搜索 219
9.2.4 解答本節(jié)開篇問題 220
9.2.5 內(nèi)容小結(jié) 220
9.2.6 思考題 220
9.3 拓?fù)渑判颍喝绾未_定代碼源文件的編譯依賴關(guān)系 221
9.3.1 什么是拓?fù)渑判颉?21
9.3.2 利用Kahn算法實(shí)現(xiàn)拓?fù)渑判颉?22
9.3.3 利用深度優(yōu)先搜索實(shí)現(xiàn)拓?fù)渑判颉?22
9.3.4 利用拓?fù)渑判驒z測(cè)環(huán) 223
9.3.5 解答本節(jié)開篇問題 224
9.3.6 內(nèi)容小結(jié) 224
9.3.7 思考題 224
9.4 單源最短路徑：地圖軟件如何“計(jì)算”最優(yōu)出行路線 225
9.4.1 最短路徑算法介紹 225
9.4.2 Dijkstra算法的原理與實(shí)現(xiàn) 225
9.4.3 Dijkstra算法的性能分析 228
9.4.4 Dijkstra算法思想的應(yīng)用 228
9.4.5 解答本節(jié)開篇問題 229
9.4.6 內(nèi)容小結(jié) 230
9.4.7 思考題 230
9.5 多源最短路徑：如何利用Floyd算法解決傳遞閉包問題 231
9.5.1 Floyd算法的原理與實(shí)現(xiàn) 231
9.5.2 Floyd算法的性能分析 232
9.5.3 利用Floyd算法求解傳遞閉包 232
9.5.4 內(nèi)容小結(jié) 233
9.5.5 思考題 233
9.6 啟發(fā)式搜索：如何用A*算法實(shí)現(xiàn)游戲中的尋路功能 233
9.6.1 什么是次優(yōu)路線 234
9.6.2 A*算法的原理與實(shí)現(xiàn) 234
9.6.3 A*算法與Dijkstra算法的對(duì)比 236
9.6.4 解答本節(jié)開篇問題 237
9.6.5 內(nèi)容小結(jié) 237
9.6.6 思考題 238
9.7 最小生成樹：如何隨機(jī)生成游戲中的迷宮地圖 238
9.7.1 什么是最小生成樹 238
9.7.2 Kruskal算法的原理與實(shí)現(xiàn) 239
9.7.3 Prim算法的原理與實(shí)現(xiàn) 240
9.7.4 解答本節(jié)開篇問題 242
9.7.5 內(nèi)容小結(jié) 244
9.7.6 思考題 245
9.8 最大流：如何解決單身交友聯(lián)誼中的最多匹配問題 245
9.8.1 什么是最大流 245
9.8.2 Ford-Fulkerson方法 246
9.8.3 Edmonds-Karp算法 247
9.8.4 最大二分匹配 249
9.8.5 解答本節(jié)開篇問題 249
9.8.6 內(nèi)容小結(jié) 249
9.8.7 思考題 250
第10章 貪心、分治、回溯和動(dòng)態(tài)規(guī)劃 251
10.1 貪心算法：如何利用貪心算法實(shí)現(xiàn)霍夫曼編碼 252
10.1.1 如何理解貪心算法 252
10.1.2 貪心算法的應(yīng)用示例 253
10.1.3 解答本節(jié)開篇問題 255
10.1.4 內(nèi)容小結(jié) 256
10.1.5 思考題 256
10.2 分治算法：談一談大規(guī)模計(jì)算框架MapReduce中的分治思想 256
10.2.1 如何理解分治算法 257
10.2.2 分治算法的應(yīng)用示例 257
10.2.3 分治算法在大數(shù)據(jù)處理中的應(yīng)用 259
10.2.4 解答本節(jié)開篇問題 259
10.2.5 內(nèi)容小結(jié) 260
10.2.6 思考題 260
10.3 回溯算法：從電影《蝴蝶效應(yīng)》中學(xué)習(xí)回溯算法的核心思想 260
10.3.1 如何理解回溯算法 261
10.3.2 八皇后問題 261
10.3.3 0-1背包問題 262
10.3.4 正則表達(dá)式匹配問題 263
10.3.5 內(nèi)容小結(jié) 264
10.3.6 思考題 264
10.4 初識(shí)動(dòng)態(tài)規(guī)劃：如何巧妙解決“雙11”購(gòu)物時(shí)的湊單問題 264
10.4.1 動(dòng)態(tài)規(guī)劃的學(xué)習(xí)路線 265
10.4.2 利用動(dòng)態(tài)規(guī)劃解決0-1背包問題 265
10.4.3 0-1背包問題的升級(jí)版 269
10.4.4 解答本節(jié)開篇問題 270
10.4.5 內(nèi)容小結(jié) 271
10.4.6 思考題 272
10.5 動(dòng)態(tài)規(guī)劃理論：徹底理解最優(yōu)子結(jié)構(gòu)、無后效性和重復(fù)子問題 272
10.5.1 “一個(gè)模型和三個(gè)特征”理論介紹 272
10.5.2 “一個(gè)模型和三個(gè)特征”的應(yīng)用示例 273
10.5.3 動(dòng)態(tài)規(guī)劃的兩種解題方法 274
10.5.4 4種算法思想的比較分析 277
10.5.5 內(nèi)容小結(jié) 277
10.5.6 思考題 278
10.6 動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：如何實(shí)現(xiàn)搜索引擎中的拼寫糾錯(cuò)功能 278
10.6.1 如何量化兩個(gè)字符串的相似度 278
10.6.2 如何通過編程計(jì)算萊文斯坦距離 279
10.6.3 如何通過編程計(jì)算最長(zhǎng)公共子串長(zhǎng)度 281
10.6.4 解答本節(jié)開篇問題 282
10.6.5 內(nèi)容小結(jié) 283
10.6.6 思考題 283
第11章 數(shù)據(jù)結(jié)構(gòu)和算法實(shí)戰(zhàn) 284
11.1 實(shí)戰(zhàn)1：剖析Redis的常用數(shù)據(jù)類型對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu) 285
11.1.1 Redis數(shù)據(jù)庫(kù)介紹 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 數(shù)據(jù)結(jié)構(gòu)的持久化問題 287
11.1.7 總結(jié)和引申 288
11.1.8 思考題 288
11.2 實(shí)戰(zhàn)2：剖析搜索引擎背后的經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法 288
11.2.1 搜索引擎系統(tǒng)的整體介紹 288
11.2.2 搜集 289
11.2.3 分析 290
11.2.4 索引 292
11.2.5 查詢 292
11.2.6 總結(jié)和引申 293
11.2.7 思考題 293
11.3 實(shí)戰(zhàn)3：剖析微服務(wù)鑒權(quán)和限流背后的數(shù)據(jù)結(jié)構(gòu)和算法 293
11.3.1 鑒權(quán)背景介紹 294
11.3.2 如何實(shí)現(xiàn)快速鑒權(quán) 294
11.3.3 限流背景介紹 297
11.3.4 如何實(shí)現(xiàn)精準(zhǔn)限流 297
11.3.5 總結(jié)和引申 298
11.3.6 思考題 299
11.4 實(shí)戰(zhàn)4：用學(xué)過的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)短網(wǎng)址服務(wù) 299
11.4.1 短網(wǎng)址服務(wù)的整體介紹 299
11.4.2 通過哈希算法生成短網(wǎng)址 299
11.4.3 通過ID生成器生成短網(wǎng)址 302
11.4.4 總結(jié)和引申 303
11.4.5 思考題 303
附錄A 思考題答案 304
書單推薦
