算法訓練營：海量圖解 + 競賽刷題 (入門篇)

陳小玉
高級程序員，主要研究方向為算法優化和機器學習。
出版著作有《趣學算法》《趣學數據結構》《算法訓練營：海量圖解+競賽刷題（入門篇）》《算法訓練營：海量圖解+競賽刷題（進階篇）》，所教學生多次獲得ACM、藍橋杯等算法競賽獎項。

第1章語言基礎... 1
1.1 開啟算法之旅：hello world! 1
1.2 常見數據類型及其表達範圍... 2
1.3 玩轉輸入輸出... 2
1.4 人生就是不斷地選擇：if…else. 9
1.5 每天都有很多次重複：for/while. 13
1.6 如何輕鬆寫一個函數... 20
1.7 從前有座山，山里有座廟：遞歸之法... 25
1.8 信息攜帶者：定義一個結構體... 29
1.9 巧用數組——好玩貪吃蛇... 31
1.10 玩轉字符串——不一樣的風格... 37

第2章算法入門... 42
2.1 算法之美... 42
2.1.1 如何評價一個算法的優劣... 42
2.1.2 算法複雜度的計算方法... 45
2.2 貪心算法... 48
2.2.1 貪心本質... 48
2.2.2 最優裝載問題... 49
2.3 分治算法... 51
2.3.1 分治算法秘籍... 51
2.3.2 合併排序... 51
2.3.3 快速排序... 57
2.4 STL應用... 65
2.4.1 vector 65
訓練間諜... 67
2.4.2 棧... 68
訓練Web導航... 69
2.4.3 queue. 75
訓練騎士移動... 75
2.4.4 list 77
訓練士兵隊列訓練... 78
2.4.5 deque. 79
訓練度度熊學隊列... 80
2.4.6 priority_queue. 82
訓練黑盒子... 83
2.4.7 bitset 85
訓練集合運算... 88
2.4.8 set/multiset 90
訓練1 集合合併... 91
訓練2 並行處理... 92
2.4.9 map/multimap. 94
訓練1 硬木種類... 96
訓練2 雙重隊列... 97
訓練3 水果... 99
2.4.10 STL的常用函數... 100
訓練1 差的中位數... 106
訓練2 中位數... 108
訓練3 訂單管理... 109
訓練4 字謎... 110

第3章線性表的應用... 112
3.1 順序表... 112
3.2 單鍊錶... 116
3.3 雙向鍊錶... 119
3.4 循環鍊錶... 122
3.5 靜態鍊錶... 123
訓練1 區塊世界... 126
訓練2 悲劇文本... 132
訓練3 移動盒子... 133

第4章棧和隊列的應用... 140
4.1 順序棧... 140
4.2 鏈棧... 143
4.3 順序隊列... 146
4.4 鏈隊列... 155
訓練1 括號匹配... 158
訓練2 鐵軌... 160
訓練3 矩陣連乘... 164
訓練4 打印隊列... 168
訓練5 並發模擬器... 171

第5章樹的應用... 187
5.1 樹... 187
5.1.1 樹的存儲... 190
5.1.2 樹、森林與二叉樹的轉換... 193
5.2 二叉樹... 194
5.2.1 二叉樹的性質... 195
5.2.2 二叉樹的存儲結構... 200
5.2.3 二叉樹的創建... 202
5.3 二叉樹遍歷... 210
5.3.1 先序遍歷... 210
5.3.2 中序遍歷... 214
5.3.3 後序遍歷... 217
5.3.4 層次遍歷... 221
5.3.5 遍歷序列還原樹... 224
訓練1 新二叉樹... 228
訓練2 還原樹... 229
訓練3 樹... 230
5.4 哈夫曼樹... 232
原理哈夫曼編碼... 232
訓練1 圍欄修復... 245
訓練2 信息熵... 246
訓練3 轉換哈夫曼編碼... 248
訓練4 可變基哈夫曼編碼... 251

第6章圖論基礎... 256
6.1 圖的存儲... 257
6.1.1 鄰接矩陣... 257
6.1.2 邊集數組... 263
6.1.3 鄰接表... 263
6.1.4 鍊式前向星... 271
訓練1 最大的節點... 274
訓練2 有向圖D和E. 276
訓練3 奶牛排序... 278
6.2 圖的遍歷... 279
6.2.1 廣度優先遍歷... 279
6.2.2 深度優先遍歷... 283
訓練1 油田... 287
訓練2 理想路徑... 290
訓練3 騎士的旅程... 293
訓練4 抓住那頭牛... 295
6.3 圖的連通性... 298
6.3.1 連通性的相關知識... 298
6.3.2 Tarjan算法... 302
訓練1 電話網絡... 306
訓練2 道路建設... 308
訓練3 圖的底部... 311
訓練4 校園網絡... 313

第7章圖的應用... 316
7.1 最短路徑... 316
7.1.1 Dijkstra算法... 316
7.1.2 Floyd算法... 322
7.1.3 Bellman-Ford算法... 326
7.1.4 SPFA算法... 328
訓練1 重型運輸... 329
訓練2 貨幣兌換... 331
訓練3 蟲洞... 332
訓練4 最短路徑... 335
7.2 最小生成樹... 336
7.2.1 Prim算法... 337
7.2.2 Kruskal算法... 346
訓練1 叢林之路... 351
訓練2 聯網... 352
訓練3 空間站... 354
訓練4 道路建設... 356
7.3 拓撲排序... 358
原理拓撲排序... 358
訓練1 家族樹... 362
訓練2 全排序... 364
訓練3 標籤球... 366
訓練4 秩序... 369
7.4 關鍵路徑... 371
原理關鍵路徑... 371
訓練1 關鍵路徑... 380
訓練2 指令安排... 382
訓練3 家務瑣事... 384
訓練4 免費DIY之旅... 385
訓練5 遊戲玩家... 388

第8章查找算法... 391
8.1 哈希表... 391
8.1.1 散列函數... 392
8.1.2 處理衝突的方法... 394
8.1.3 散列查找及性能分析... 404
訓練1 雪花... 406
訓練2 公式... 407
訓練3 正方形... 409
8.2 字符串模式匹配... 411
8.2.1 BF算法... 412
8.2.2 KMP算法... 415
訓練1 統計單詞數... 421
訓練2 KMP字符串匹配... 423
8.3 二叉查找樹... 424
原理二叉查找樹詳解... 424
訓練1 落葉... 436
訓練2 完全二叉搜索樹... 439
訓練3 硬木種類... 441
訓練4 二叉搜索樹... 442
8.4 平衡二叉樹... 444
原理AVL樹詳解... 445
訓練1 平衡二叉樹... 458
訓練2 雙重隊列... 461
訓練3 黑盒子... 464
訓練4 硬木種類... 465

第9章搜索技術... 466
9.1 二分搜索... 466
原理二分搜索技術... 466
訓練1 跳房子遊戲... 471
訓練2 烘乾衣服... 475
訓練3 花環... 477
訓練4 電纜切割... 479
9.2 深度優先搜索... 480
9.2.1 回溯法... 480
9.2.2 子集樹... 483
9.2.3 m叉樹... 491
9.2.4 排列樹... 499
訓練1 魅力手鐲... 515
訓練2 圖的m著色問題... 516
訓練3 N皇后問題... 517
9.2.5 DFS+剪枝優化... 517
訓練1 數獨遊戲... 518
訓練2 生日蛋糕... 521
訓練3 木棒... 522
9.3 廣度優先搜索... 524
9.3.1 分支限界法... 525
9.3.2 隊列式廣度優先搜索.... 525
9.3.3 優先隊列式廣度優先搜索... 535
訓練1 迷宮問題... 541
訓練2 加滿油箱... 542
9.3.4 嵌套廣度優先搜索... 545
訓練推箱子... 545
9.3.5 雙向廣度優先搜索... 549
訓練魔鬼Ⅱ... 549
9.4 啟發式搜索... 551
9.4.1 A*算法... 552
9.4.2 IDA*算法... 552
訓練1 八數碼... 552
訓練2 八數碼II 562
訓練3 第K短路... 565
訓練4 冪運算... 567