秒懂算法：用常識(shí)解讀數(shù)據(jù)結(jié)構(gòu)與算法（圖靈出品）

第 1 章 數(shù)據(jù)結(jié)構(gòu)為何重要 1
1．1 數(shù)據(jù)結(jié)構(gòu) 2
1．2 數(shù)組：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) 3
1．3 速度計(jì)量 4
1．4 讀取 4
1．5 查找 7
1．6 插入 9
1．7 刪除 11
1．8 集合：差之毫厘，“慢”之千里 12
1．9 小結(jié) 15
習(xí)題 15
第 2 章 算法為何重要 17
2．1 有序數(shù)組 18
2．2 有序數(shù)組的查找 20
2．3 二分查找 21
2．4 二分查找與線性查找 25
2．5 小結(jié) 27
習(xí)題 28
第 3 章 哦！大O記法 29
3．1 大O：對(duì)N個(gè)元素來說需要多少步 29
3．2 大O的靈魂 30
3．2．1 深入大O的靈魂 32
3．2．2 同樣的算法，不同的場(chǎng)景 32
3．3 第三類算法 33
3．4 對(duì)數(shù) 34
3．5 O(log N)的含義 34
3．6 實(shí)際例子 35
3．7 小結(jié) 36
習(xí)題 36
第 4 章 使用大O給代碼提速 38
4．1 冒泡排序 38
4．2 冒泡排序?qū)崙?zhàn) 39
4．3 冒泡排序的效率 44
4．4 平方問題 45
4．5 線性解法 47
4．6 小結(jié) 48
習(xí)題 49
第 5 章 用或不用大O來優(yōu)化代碼 50
5．1 選擇排序 50
5．2 選擇排序?qū)崙?zhàn) 51
5．3 選擇排序的效率 55
5．4 忽略常數(shù) 56
5．5 大O類別 57
5．5．1 實(shí)際例子 58
5．5．2 關(guān)鍵步驟 59
5．6 小結(jié) 59
習(xí)題 60
第 6 章 根據(jù)情況進(jìn)行優(yōu)化 61
6．1 插入排序 61
6．2 插入排序?qū)崙?zhàn) 62
6．3 插入排序的效率 67
6．4 平均情況 68
6．5 實(shí)際例子 70
6．6 小結(jié) 72
習(xí)題 72
第 7 章 日常代碼中的大O 74
7．1 偶數(shù)平均數(shù) 74
7．2 構(gòu)詞程序 75
7．3 數(shù)組抽樣 77
7．4 攝氏溫度平均值 78
7．5 衣服標(biāo)簽 79
7．6 1的個(gè)數(shù) 80
7．7 回文檢查 80
7．8 計(jì)算所有的積 81
7．9 密碼破解程序 84
7．10 小結(jié) 86
習(xí)題 86
第 8 章 查找迅速的哈希表 89
8．1 哈希表 89
8．2 用哈希函數(shù)進(jìn)行哈希 90
8．3 好玩又賺錢的同義詞典（賺錢是重點(diǎn)） 91
8．4 哈希表查找 92
8．5 解決沖突 94
8．6 創(chuàng)造高效的哈希表 96
8．7 用哈希表整合數(shù)據(jù) 98
8．8 用哈希表優(yōu)化速度 99
8．9 小結(jié) 103
習(xí)題 103
第 9 章 用棧和隊(duì)列打造優(yōu)雅的代碼 104
9．1 棧 104
9．2 抽象數(shù)據(jù)類型 106
9．3 棧實(shí)戰(zhàn) 107
9．4 受限數(shù)據(jù)結(jié)構(gòu)的重要性 112
9．5 隊(duì)列 113
9．6 隊(duì)列實(shí)戰(zhàn) 114
9．7 小結(jié) 116
習(xí)題 116
第 10 章 用遞歸不停遞歸 117
10．1 用遞歸代替循環(huán) 117
10．2 基準(zhǔn)情形 118
10．3 閱讀遞歸代碼 119
10．4 計(jì)算機(jī)眼中的遞歸 121
10．4．1 調(diào)用棧 121
10．4．2 棧溢出 123
10．5 文件系統(tǒng)遍歷 123
10．6 小結(jié) 125
習(xí)題 125
第 11 章 學(xué)習(xí)編寫遞歸代碼 127
11．1 遞歸類別：重復(fù)執(zhí)行 127
11．2 遞歸類別：計(jì)算 130
11．3 自上而下遞歸：新的思維方式 132
11．3．1 自上而下的思考過程 133
11．3．2 數(shù)組的和 133
11．3．3 字符串倒序 134
11．3．4 x的個(gè)數(shù) 135
11．4 臺(tái)階問題 136
11．5 易位構(gòu)詞生成 139
11．6 小結(jié) 142
習(xí)題 143
第 12 章 動(dòng)態(tài)規(guī)劃 144
12．1 不必要的遞歸調(diào)用 144
12．2 大O小改 147
12．3 遞歸的效率 148
12．4 重復(fù)子問題 149
12．5 動(dòng)態(tài)規(guī)劃與記憶化 150
12．6 自下而上的動(dòng)態(tài)規(guī)劃 153
12．6．1 自下而上的斐波那契函數(shù) 154
12．6．2 記憶化與自下而上 154
12．7 小結(jié) 155
習(xí)題 155
第 13 章 飛快的遞歸算法 156
13．1 分區(qū) 156
13．2 快速排序 161
13．3 快速排序的效率 165
13．3．1 快速排序鳥瞰 166
13．3．2 快速排序的時(shí)間復(fù)雜度 167
13．4 最壞情況下的快速排序 169
13．5 快速選擇 171
13．5．1 快速選擇的效率 172
13．5．2 代碼實(shí)現(xiàn)：快速選擇 173
13．6 基于排序的其他算法 173
13．7 小結(jié) 175
習(xí)題 175
第 14 章 基于節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) 176
14．1 鏈表 176
14．2 鏈表實(shí)現(xiàn) 177
14．3 讀取 179
14．4 查找 180
14．5 插入 181
14．6 刪除 185
14．7 鏈表操作的效率 187
14．8 鏈表實(shí)戰(zhàn) 187
14．9 雙鏈表 188
14．9．1 代碼實(shí)現(xiàn)：雙鏈表插入 189
14．9．2 前后移動(dòng) 190
14．10 隊(duì)列的雙鏈表實(shí)現(xiàn) 190
14．11 小結(jié) 192
習(xí)題 192
第 15 章 用二叉查找樹加速萬物 193
15．1 樹 193
15．2 二叉查找樹 195
15．3 查找 196
15．3．1 二叉查找樹的查找效率 198
15．3．2 logN層 198
15．3．3 代碼實(shí)現(xiàn)：二叉查找樹查找 199
15．4 插入 200
15．4．1 代碼實(shí)現(xiàn)：二叉查找樹插入 202
15．4．2 插入順序 203
15．5 刪除 203
15．5．1 刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 204
15．5．2 找到后繼節(jié)點(diǎn) 205
15．5．3 有右子節(jié)點(diǎn)的后繼節(jié)點(diǎn) 206
15．5．4 完整的刪除算法 208
15．5．5 代碼實(shí)現(xiàn)：二叉查找樹刪除 208
15．5．6 二叉查找樹刪除的效率 211
15．6 二叉查找樹實(shí)戰(zhàn) 211
15．7 二叉查找樹遍歷 212
15．8 小結(jié) 215
習(xí)題 216
第 16 章 使用堆分清主次 217
16．1 優(yōu)先隊(duì)列 217
16．2 堆 218
16．2．1 堆條件 219
16．2．2 完全樹 220
16．3 堆的性質(zhì) 221
16．4 堆的插入 222
16．5 尋找尾節(jié)點(diǎn) 223
16．6 堆的刪除 224
16．7 堆和有序數(shù)組 227
16．8 重新解決尾節(jié)點(diǎn)問題 228
16．9 用數(shù)組實(shí)現(xiàn)堆 230
16．9．1 遍歷基于數(shù)組的堆 231
16．9．2 代碼實(shí)現(xiàn)：堆插入 232
16．9．3 代碼實(shí)現(xiàn)：堆刪除 233
16．9．4 堆的其他實(shí)現(xiàn)方法 235
16．10 用堆實(shí)現(xiàn)優(yōu)先隊(duì)列 235
16．11 小結(jié) 236
習(xí)題 236
第 17 章 字典樹又何妨 237
17．1 字典樹 237
17．1．1 字典樹節(jié)點(diǎn) 238
17．1．2 Trie類 238
17．2 存儲(chǔ)單詞 239
17．3 字典樹查找 241
17．4 字典樹查找的效率 245
17．5 字典樹插入 246
17．6 實(shí)現(xiàn)自動(dòng)補(bǔ)全 249
17．6．1 收集所有單詞 249
17．6．2 遞歸過程分析 251
17．7 完成自動(dòng)補(bǔ)全功能 254
17．8 帶有值的字典樹：更好的自動(dòng)補(bǔ)全 255
17．9 小結(jié) 256
習(xí)題 257
第 18 章 連接萬物的圖 258
18．1 圖 258
18．1．1 圖和樹 259
18．1．2 圖的術(shù)語 259
18．1．3 圖的基本實(shí)現(xiàn) 260
18．2 有向圖 260
18．3 面向?qū)ο蟮膱D實(shí)現(xiàn) 261
18．4 圖的搜索 262
18．5 深度優(yōu)先搜索 264
18．5．1 深度優(yōu)先搜索步驟詳解 265
18．5．2 代碼實(shí)現(xiàn)：深度優(yōu)先搜索 271
18．6 廣度優(yōu)先搜索 272
18．6．1 廣度優(yōu)先搜索步驟詳解 273
18．6．2 代碼實(shí)現(xiàn)：廣度優(yōu)先搜索 280
18．6．3 對(duì)比廣度優(yōu)先搜索與深度優(yōu)先搜索 281
18．7 圖的搜索效率 283
18．8 加權(quán)圖 285
18．8．1 加權(quán)圖的代碼實(shí)現(xiàn) 286
18．8．2 最短路徑問題 287
18．9 迪杰斯特拉算法 288
18．9．1 迪杰斯特拉算法的準(zhǔn)備工作 288
18．9．2 迪杰斯特拉算法的步驟 289
18．9．3 迪杰斯特拉算法詳解 289
18．9．4 找到最短路徑 295
18．9．5 代碼實(shí)現(xiàn)：迪杰斯特拉算法 296
18．9．6 迪杰斯特拉算法的效率 301
18．10 小結(jié) 301
習(xí)題 302
第 19 章 對(duì)付空間限制 304
19．1 空間復(fù)雜度的大O記法 304
19．2 時(shí)間和空間的取舍 306
19．3 遞歸的隱藏成本 308
19．4 小結(jié) 310
習(xí)題 310
第 20 章 代碼優(yōu)化技巧 312
20．1 前置工作：確定目前的時(shí)間復(fù)雜度 312
20．2 從這里開始：最理想復(fù)雜度 312
20．3 魔法查找 313
20．3．1 魔法查找：查找作者 314
20．3．2 使用其他數(shù)據(jù)結(jié)構(gòu) 315
20．3．3 兩數(shù)之和問題 317
20．4 找規(guī)律 319
20．4．1 硬幣游戲 319
20．4．2 舉例法 320
20．4．3 交換和問題 321
20．5 貪心算法 325
20．5．1 數(shù)組最大值 326
20．5．2 最大子數(shù)組和 326
20．5．3 貪心的股價(jià)預(yù)測(cè) 331
20．6 更換數(shù)據(jù)結(jié)構(gòu) 335
20．6．1 易位構(gòu)詞檢查器 335
20．6．2 分組排序 338
20．7 小結(jié) 340
20．8 臨別感言 340
習(xí)題 341
附錄 習(xí)題答案（圖靈社區(qū)下載）