秒懂算法：用常識解讀數據結構與算法

【作者简介】

杰伊·温格罗（Jay Wengrow）

经验丰富的讲师、软件工程师，一直致力于全民编程教育，编程培训公司Actualize和Anyone Can Learn to Code的创始人兼CEO。

【译者简介】

姜喆

普渡大学计算机科学硕士，具备扎实的数据结构与算法基础，熟悉C、JavaScript、Java和Python。曾在互联网行业和金融行业从事软件开发工作，现就职于游戏公司。另译有《不可能的几何挑战：数学求索两千年》。

第 1 章 數據結構為何重要 1

1.1 數據結構 2

1.2 數組：基礎數據結構 3

1.3 速度計量 4

1.4 讀取 4

1.5 查找 7

1.6 插入 9

1.7 刪除 11

1.8 集合：差之毫釐，“慢”之千里 12

1.9 小結 15

習題 15

第 2 章 算法為何重要 17

2.1 有序數組 18

2.2 有序數組的查找 20

2.3 二分查找 21

2.4 二分查找與線性查找 25

2.5 小結 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 對數 34

3.5 O(log N)的含義 34

3.6 實際例子 35

3.7 小結 36

習題 36

第 4 章 使用大O給代碼提速 38

4.1 冒泡排序 38

4.2 冒泡排序實戰 39

4.3 冒泡排序的效率 44

4.4 平方問題 45

4.5 線性解法 47

4.6 小結 48

習題 49

第 5 章 用或不用大O來優化代碼 50

5.1 選擇排序 50

5.2 選擇排序實戰 51

5.3 選擇排序的效率 55

5.4 忽略常數 56

5.5 大O類別 57

5.5.1 實際例子 58

5.5.2 關鍵步驟 59

5.6 小結 59

習題 60

第 6 章 根據情況進行優化 61

6.1 插入排序 61

6.2 插入排序實戰 62

6.3 插入排序的效率 67

6.4 平均情況 68

6.5 實際例子 70

6.6 小結 72

習題 72

第 7 章 日常代碼中的大O 74

7.1 偶數平均數 74

7.2 構詞程序 75

7.3 數組抽樣 77

7.4 攝氏溫度平均值 78

7.5 衣服標簽 79

7.6 1的個數 80

7.7 迴文檢查 80

7.8 計算所有的積 81

7.9 密碼破解程序 84

7.10 小結 86

習題 86

第 8 章 查找迅速的哈希表 89

8.1 哈希表 89

8.2 用哈希函數進行哈希 90

8.3 好玩又賺錢的同義詞典（賺錢是重點） 91

8.4 哈希表查找 92

8.5 解決沖突 94

8.6 創造高效的哈希表 96

8.7 用哈希表整合數據 98

8.8 用哈希表優化速度 99

8.9 小結 103

習題 103

第 9 章 用棧和隊列打造優雅的代碼 104

9.1 棧 104

9.2 抽象數據類型 106

9.3 棧實戰 107

9.4 受限數據結構的重要性 112

9.5 隊列 113

9.6 隊列實戰 114

9.7 小結 116

習題 116

第 10 章 用遞歸不停遞歸 117

10.1 用遞歸代替循環 117

10.2 基準情形 118

10.3 閱讀遞歸代碼 119

10.4 電腦眼中的遞歸 121

10.4.1 調用棧 121

10.4.2 棧溢出 123

10.5 文件系統遍歷 123

10.6 小結 125

習題 125

第 11 章 學習編寫遞歸代碼 127

11.1 遞歸類別：重復執行 127

11.2 遞歸類別：計算 130

11.3 自上而下遞歸：新的思維方式 132

11.3.1 自上而下的思考過程 133

11.3.2 數組的和 133

11.3.3 字符串倒序 134

11.3.4 x的個數 135

11.4 台階問題 136

11.5 易位構詞生成 139

11.6 小結 142

習題 143

第 12 章 動態規劃 144

12.1 不必要的遞歸調用 144

12.2 大O小改 147

12.3 遞歸的效率 148

12.4 重復子問題 149

12.5 動態規劃與記憶化 150

12.6 自下而上的動態規劃 153

12.6.1 自下而上的斐波那契函數 154

12.6.2 記憶化與自下而上 154

12.7 小結 155

習題 155

第 13 章 飛快的遞歸算法 156

13.1 分區 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 代碼實現：快速選擇 173

13.6 基於排序的其他算法 173

13.7 小結 175

習題 175

第 14 章 基於節點的數據結構 176

14.1 鏈表 176

14.2 鏈表實現 177

14.3 讀取 179

14.4 查找 180

14.5 插入 181

14.6 刪除 185

14.7 鏈表操作的效率 187

14.8 鏈表實戰 187

14.9 雙鏈表 188

14.9.1 代碼實現：雙鏈表插入 189

14.9.2 前後移動 190

14.10 隊列的雙鏈表實現 190

14.11 小結 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 代碼實現：二叉查找樹查找 199

15.4 插入 200

15.4.1 代碼實現：二叉查找樹插入 202

15.4.2 插入順序 203

15.5 刪除 203

15.5.1 刪除有兩個子節點的節點 204

15.5.2 找到後繼節點 205

15.5.3 有右子節點的後繼節點 206

15.5.4 完整的刪除算法 208

15.5.5 代碼實現：二叉查找樹刪除 208

15.5.6 二叉查找樹刪除的效率 211

15.6 二叉查找樹實戰 211

15.7 二叉查找樹遍歷 212

15.8 小結 215

習題 216

第 16 章 使用堆分清主次 217

16.1 優先隊列 217

16.2 堆 218

16.2.1 堆條件 219

16.2.2 完全樹 220

16.3 堆的性質 221

16.4 堆的插入 222

16.5 尋找尾節點 223

16.6 堆的刪除 224

16.7 堆和有序數組 227

16.8 重新解決尾節點問題 228

16.9 用數組實現堆 230

16.9.1 遍歷基於數組的堆 231

16.9.2 代碼實現：堆插入 232

16.9.3 代碼實現：堆刪除 233

16.9.4 堆的其他實現方法 235

16.10 用堆實現優先隊列 235

16.11 小結 236

習題 236

第 17 章 字典樹又何妨 237

17.1 字典樹 237

17.1.1 字典樹節點 238

17.1.2 Trie類 238

17.2 存儲單詞 239

17.3 字典樹查找 241

17.4 字典樹查找的效率 245

17.5 字典樹插入 246

17.6 實現自動補全 249

17.6.1 收集所有單詞 249

17.6.2 遞歸過程分析 251

17.7 完成自動補全功能 254

17.8 帶有值的字典樹：更好的自動補全 255

17.9 小結 256

習題 257

第 18 章 連接萬物的圖 258

18.1 圖 258

18.1.1 圖和樹 259

18.1.2 圖的術語 259

18.1.3 圖的基本實現 260

18.2 有向圖 260

18.3 面向對象的圖實現 261

18.4 圖的搜索 262

18.5 深度優先搜索 264

18.5.1 深度優先搜索步驟詳解 265

18.5.2 代碼實現：深度優先搜索 271

18.6 廣度優先搜索 272

18.6.1 廣度優先搜索步驟詳解 273

18.6.2 代碼實現：廣度優先搜索 280

18.6.3 對比廣度優先搜索與深度優先搜索 281

18.7 圖的搜索效率 283

18.8 加權圖 285

18.8.1 加權圖的代碼實現 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 代碼實現：迪傑斯特拉算法 296

18.9.6 迪傑斯特拉算法的效率 301

18.10 小結 301

習題 302

第 19 章 對付空間限制 304

19.1 空間復雜度的大O記法 304

19.2 時間和空間的取捨 306

19.3 遞歸的隱藏成本 308

19.4 小結 310

習題 310

第 20 章 代碼優化技巧 312

20.1 前置工作：確定目前的時間復雜度 312

20.2 從這里開始：最理想復雜度 312

20.3 魔法查找 313

20.3.1 魔法查找：查找作者 314

20.3.2 使用其他數據結構 315

20.3.3 兩數之和問題 317

20.4 找規律 319

20.4.1 硬幣游戲 319

20.4.2 舉例法 320

20.4.3 交換和問題 321

20.5 貪心算法 325

20.5.1 數組最大值 326

20.5.2 最大子數組和 326

20.5.3 貪心的股價預測 331

20.6 更換數據結構 335

20.6.1 易位構詞檢查器 335

20.6.2 分組排序 338

20.7 小結 340

20.8 臨別感言 340

習題 341

附錄 習題答案（圖靈社區下載）