數(shù)據(jù)結(jié)構(gòu)與算法之美（全彩印刷）
定 價(jià)：119.8 元
- 作者：王爭(zhēng)（@小爭(zhēng)哥）
- 出版時(shí)間：2021/6/1
- ISBN：9787115562050
- 出 版 社：人民郵電出版社
- 中圖法分類：TP311.12
- 頁(yè)碼：334
- 紙張：
- 版次：01
- 開(kāi)本：16開(kāi)
內(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)典排序、二分查找及二分查找的變體問(wèn)題。第4章介紹哈希表、位圖、哈希算法和布隆過(guò)濾器。第5章介紹樹(shù)相關(guān)的數(shù)據(jù)結(jié)構(gòu)，包括二叉樹(shù)、二叉查找樹(shù)、平衡二叉查找樹(shù)、遞歸樹(shù)和B+樹(shù)。第6章介紹堆，以及堆的各種應(yīng)用，包括堆排序、優(yōu)先級(jí)隊(duì)列、求Top K、求中位數(shù)和求百分位數(shù)。第7章介紹跳表、并查集、線段樹(shù)和樹(shù)狀數(shù)組這些比較高級(jí)的數(shù)據(jù)結(jié)構(gòu)。第8章介紹字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie樹(shù)和AC自動(dòng)機(jī)。第9章介紹圖及相關(guān)算法，包括深度優(yōu)先搜索、廣度優(yōu)先搜索、拓?fù)渑判颉ijkstra算法、Floyd算法、A*算法、最小生成樹(shù)算法、最大流算法和最大二分匹配等。第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語(yǔ)言編寫，但本書講解的知識(shí)與具體編程語(yǔ)言無(wú)關(guān)，因此，本書不但適合各種類型的研發(fā)工程師，而且可以作為高校計(jì)算機(jī)相關(guān)專業(yè)師生的學(xué)習(xí)用書和培訓(xùn)學(xué)校的教材。
1.好評(píng)爆表的極客時(shí)間算法專欄網(wǎng)紅達(dá)人，GitHub上算法教程Star數(shù)量上萬(wàn)的作者新作；
2.10多萬(wàn)人驗(yàn)證過(guò)的、為求職面試者、工程師量身打造的數(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 幾種常見(jiàn)的時(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開(kāi)始編號(hào) 14
2.1.1 數(shù)組的定義 14
2.1.2 尋址公式和隨機(jī)訪問(wèn)特性 15
2.1.3 低效的插入和刪除操作 15
2.1.4 警惕數(shù)組訪問(wèn)越界問(wèn)題 16
2.1.5 容器能否完全替代數(shù)組 17
2.1.6 解答本節(jié)開(kāi)篇問(wèn)題 18
2.1.7 內(nèi)容小結(jié) 18
2.1.8 思考題 18
2.2 數(shù)組（下）：數(shù)據(jù)結(jié)構(gòu)中的數(shù)組和編程語(yǔ)言中的數(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é)開(kāi)篇問(wèn)題 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：多寫多練，沒(méi)有捷徑 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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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ì)算問(wèn)題 50
3.1.7 將遞歸代碼改寫為非遞歸代碼 51
3.1.8 解答本節(jié)開(kāi)篇問(wèn)題 52
3.1.9 內(nèi)容小結(jié) 52
3.1.10 思考題 52
3.2 尾遞歸：如何借助尾遞歸避免遞歸過(guò)深導(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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 71
3.5.6 內(nèi)容小結(jié) 72
3.5.7 思考題 72
3.6 線性排序：如何根據(jù)年齡給100萬(wàn)個(gè)用戶排序 72
3.6.1 桶排序 73
3.6.2 計(jì)數(shù)排序 74
3.6.3 基數(shù)排序 76
3.6.4 解答本節(jié)開(kāi)篇問(wèn)題 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 無(wú)處不在的二分思想 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é)開(kāi)篇問(wèn)題 84
3.8.6 內(nèi)容小結(jié) 85
3.8.7 思考題 85
3.9 二分查找的變體：如何快速定位IP地址對(duì)應(yīng)的歸屬地 85
3.9.1 什么是二分查找變體問(wèn)題 86
3.9.2 變體問(wèn)題1：查找第一個(gè)值等于給定值的元素 86
3.9.3 變體問(wèn)題2：查找最后一個(gè)值等于給定值的元素 88
3.9.4 變體問(wèn)題3：查找第一個(gè)值大于或等于給定值的元素 88
3.9.5 變體問(wèn)題4：查找最后一個(gè)值小于或等于給定值的元素 89
3.9.6 解答本節(jié)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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 解決裝載因子過(guò)大的問(wèn)題 97
4.2.3 避免低效的擴(kuò)容 98
4.2.4 選擇合適的沖突解決方法 99
4.2.5 工業(yè)級(jí)的哈希表舉例分析 100
4.2.6 解答本節(jié)開(kāi)篇問(wèn)題 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)頁(yè)“爬蟲”中的網(wǎng)址鏈接去重功能 106
4.4.1 基于哈希表的解決方案 106
4.4.2 基于位圖的解決方案 106
4.4.3 基于布隆過(guò)濾器的解決方案 108
4.4.4 回答本節(jié)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 116
4.5.10 內(nèi)容小結(jié) 116
4.5.11 思考題 116
第5章 樹(shù) 117
5.1 樹(shù)和二叉樹(shù)：什么樣的二叉樹(shù)適合用數(shù)組存儲(chǔ) 118
5.1.1 樹(shù)的定義 118
5.1.2 二叉樹(shù)的定義 118
5.1.3 二叉樹(shù)的存儲(chǔ) 119
5.1.4 二叉樹(shù)的遍歷 120
5.1.5 解答本節(jié)開(kāi)篇問(wèn)題 122
5.1.6 內(nèi)容小結(jié) 122
5.1.7 思考題 122
5.2 二叉查找樹(shù)：相比哈希表，二叉查找樹(shù)有何優(yōu)勢(shì) 122
5.2.1 二叉查找樹(shù)的定義和操作 123
5.2.2 支持重復(fù)數(shù)據(jù)的二叉查找樹(shù) 126
5.2.3 二叉查找樹(shù)的性能分析 126
5.2.4 解答本節(jié)開(kāi)篇問(wèn)題 127
5.2.5 內(nèi)容小結(jié) 128
5.2.6 思考題 128
5.3 平衡二叉查找樹(shù)：為什么紅黑樹(shù)如此受歡迎 128
5.3.1 平衡二叉查找樹(shù)的定義 128
5.3.2 紅黑樹(shù)的定義 129
5.3.3 紅黑樹(shù)的性能分析 129
5.3.4 解答本節(jié)開(kāi)篇問(wèn)題 130
5.3.5 內(nèi)容小結(jié) 130
5.3.6 思考題 131
5.4 遞歸樹(shù)：如何借助樹(shù)求遞歸算法的時(shí)間復(fù)雜度 131
5.4.1 遞歸樹(shù)時(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+樹(shù)：MySQL數(shù)據(jù)庫(kù)索引是如何實(shí)現(xiàn)的 135
5.5.1 典型需求：按值查詢和按區(qū)間查詢 135
5.5.2 基于哈希表和二叉查找樹(shù)的解決方案 136
5.5.3 基于B+樹(shù)的解決方案 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é)開(kāi)篇問(wèn)題 145
6.1.8 內(nèi)容小結(jié) 146
6.1.9 思考題 146
6.2 堆排序：為什么說(shuō)堆排序沒(méi)有快速排序快 147
6.2.1 堆排序之建堆 147
6.2.2 堆排序之排序 149
6.2.3 堆排序的性能分析 149
6.2.4 解答本節(jié)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 155
6.3.5 內(nèi)容小結(jié) 155
6.3.6 思考題 156
第7章 跳表、并查集、線段樹(shù)和樹(shù)狀數(shù)組 157
7.1 跳表：Redis中的有序集合類型是如何實(shí)現(xiàn)的 158
7.1.1 跳表的由來(lái) 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é)開(kāi)篇問(wèn)題 162
7.1.7 內(nèi)容小結(jié) 163
7.1.8 思考題 163
7.2 并查集：路徑壓縮和按秩合并這兩個(gè)優(yōu)化是否沖突 163
7.2.1 并查集的由來(lái) 163
7.2.2 基于鏈表的實(shí)現(xiàn)思路 164
7.2.3 基于樹(shù)的實(shí)現(xiàn)思路 166
7.2.4 內(nèi)容小結(jié) 168
7.2.5 思考題 168
7.3 線段樹(shù)：如何查找獵聘網(wǎng)中積分排在第K位的獵頭 168
7.3.1 區(qū)間統(tǒng)計(jì)問(wèn)題 169
7.3.2 線段樹(shù)的其他應(yīng)用 172
7.3.3 解答本節(jié)開(kāi)篇問(wèn)題 174
7.3.4 內(nèi)容小結(jié) 174
7.3.5 思考題 174
7.4 樹(shù)狀數(shù)組：如何實(shí)現(xiàn)一個(gè)高性能、低延遲的實(shí)時(shí)排行榜 174
7.4.1 “前綴和”問(wèn)題 175
7.4.2 樹(shù)狀數(shù)組與線段樹(shù)的對(duì)比 177
7.4.3 解答本節(jié)開(kāi)篇問(wèn)題 177
7.4.4 內(nèi)容小結(jié) 178
7.4.5 思考題 178
第8章 字符串匹配算法 179
8.1 BF算法：編程語(yǔ)言中的查找、替換函數(shù)是怎樣實(shí)現(xiàn)的 180
8.1.1 BF算法的原理與實(shí)現(xiàn) 180
8.1.2 BF算法的性能分析 181
8.1.3 解答本節(jié)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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ù)：如何實(shí)現(xiàn)搜索引擎的搜索關(guān)鍵詞提示功能 198
8.5.1 Trie樹(shù)的定義 199
8.5.2 Trie樹(shù)的代碼實(shí)現(xiàn) 200
8.5.3 Trie樹(shù)的性能分析 201
8.5.4 Trie樹(shù)與哈希表、紅黑樹(shù)的比較 202
8.5.5 解答本節(jié)開(kāi)篇問(wèn)題 202
8.5.6 內(nèi)容小結(jié) 203
8.5.7 思考題 204
8.6 AC自動(dòng)機(jī)：如何用多模式串匹配實(shí)現(xiàn)敏感詞過(guò)濾 204
8.6.1 基于單模式串的敏感詞過(guò)濾 204
8.6.2 基于Trie樹(shù)的敏感詞過(guò)濾 205
8.6.3 基于AC自動(dòng)機(jī)的敏感詞過(guò)濾 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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 229
9.4.6 內(nèi)容小結(jié) 230
9.4.7 思考題 230
9.5 多源最短路徑：如何利用Floyd算法解決傳遞閉包問(wèn)題 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é)開(kāi)篇問(wèn)題 237
9.6.5 內(nèi)容小結(jié) 237
9.6.6 思考題 238
9.7 最小生成樹(shù)：如何隨機(jī)生成游戲中的迷宮地圖 238
9.7.1 什么是最小生成樹(shù) 238
9.7.2 Kruskal算法的原理與實(shí)現(xiàn) 239
9.7.3 Prim算法的原理與實(shí)現(xiàn) 240
9.7.4 解答本節(jié)開(kāi)篇問(wèn)題 242
9.7.5 內(nèi)容小結(jié) 244
9.7.6 思考題 245
9.8 最大流：如何解決單身交友聯(lián)誼中的最多匹配問(wè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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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é)開(kāi)篇問(wèn)題 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 八皇后問(wèn)題 261
10.3.3 0-1背包問(wèn)題 262
10.3.4 正則表達(dá)式匹配問(wèn)題 263
10.3.5 內(nèi)容小結(jié) 264
10.3.6 思考題 264
10.4 初識(shí)動(dòng)態(tài)規(guī)劃：如何巧妙解決“雙11”購(gòu)物時(shí)的湊單問(wèn)題 264
10.4.1 動(dòng)態(tài)規(guī)劃的學(xué)習(xí)路線 265
10.4.2 利用動(dòng)態(tài)規(guī)劃解決0-1背包問(wèn)題 265
10.4.3 0-1背包問(wèn)題的升級(jí)版 269
10.4.4 解答本節(jié)開(kāi)篇問(wèn)題 270
10.4.5 內(nèi)容小結(jié) 271
10.4.6 思考題 272
10.5 動(dòng)態(tài)規(guī)劃理論：徹底理解最優(yōu)子結(jié)構(gòu)、無(wú)后效性和重復(fù)子問(wèn)題 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 如何通過(guò)編程計(jì)算萊文斯坦距離 279
10.6.3 如何通過(guò)編程計(jì)算最長(zhǎng)公共子串長(zhǎng)度 281
10.6.4 解答本節(jié)開(kāi)篇問(wèn)題 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)的持久化問(wèn)題 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é)過(guò)的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)短網(wǎng)址服務(wù) 299
11.4.1 短網(wǎng)址服務(wù)的整體介紹 299
11.4.2 通過(guò)哈希算法生成短網(wǎng)址 299
11.4.3 通過(guò)ID生成器生成短網(wǎng)址 302
11.4.4 總結(jié)和引申 303
11.4.5 思考題 303
附錄A 思考題答案 304
書單推薦
