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