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

第1章  語言基礎... 1
1.1  開啟算法之旅：hello world! 1
1.2  常見數(shù)據(jù)類型及其表達范圍... 2
1.3  玩轉(zhuǎn)輸入輸出... 2
1.4  人生就是不斷地選擇：if…else. 9
1.5  每天都有很多次重復：for/while. 13
1.6  如何輕松寫一個函數(shù)... 20
1.7  從前有座山，山里有座廟：遞歸之法... 25
1.8  信息攜帶者：定義一個結(jié)構體... 29
1.9  巧用數(shù)組——好玩貪吃蛇... 31
1.10  玩轉(zhuǎn)字符串——不一樣的風格... 37
 
第2章  算法入門... 42
2.1  算法之美... 42
2.1.1  如何評價一個算法的優(yōu)劣... 42
2.1.2  算法復雜度的計算方法... 45
2.2  貪心算法... 48
2.2.1  貪心本質(zhì)... 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的常用函數(shù)... 100
訓練1  差的中位數(shù)... 106
訓練2  中位數(shù)... 108
訓練3  訂單管理... 109
訓練4  字謎... 110
 
第3章  線性表的應用... 112
3.1  順序表... 112
3.2  單鏈表... 116
3.3  雙向鏈表... 119
3.4  循環(huán)鏈表... 122
3.5  靜態(tài)鏈表... 123
訓練1  區(qū)塊世界... 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  并發(fā)模擬器... 171
 
第5章  樹的應用... 187
5.1  樹... 187
5.1.1  樹的存儲... 190
5.1.2  樹、森林與二叉樹的轉(zhuǎn)換... 193
5.2  二叉樹... 194
5.2.1  二叉樹的性質(zhì)... 195
5.2.2  二叉樹的存儲結(jié)構... 200
5.2.3  二叉樹的創(chuàng)建... 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  轉(zhuǎn)換哈夫曼編碼... 248
訓練4  可變基哈夫曼編碼... 251
 
第6章  圖論基礎... 256
6.1  圖的存儲... 257
6.1.1  鄰接矩陣... 257
6.1.2  邊集數(shù)組... 263
6.1.3  鄰接表... 263
6.1.4  鏈式前向星... 271
訓練1  的節(jié)點... 274
訓練2  有向圖D和E. 276
訓練3  奶牛排序... 278
6.2  圖的遍歷... 279
6.2.1  廣度優(yōu)先遍歷... 279
6.2.2  深度優(yōu)先遍歷... 283
訓練1  油田... 287
訓練2  理想路徑... 290
訓練3  騎士的旅程... 293
訓練4  抓住那頭牛... 295
6.3  圖的連通性... 298
6.3.1  連通性的相關知識... 298
6.3.2  Tarjan算法... 302
訓練1  電話網(wǎng)絡... 306
訓練2  道路建設... 308
訓練3  圖的底部... 311
訓練4  校園網(wǎng)絡... 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  聯(lián)網(wǎng)... 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  散列函數(shù)... 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  統(tǒng)計單詞數(shù)... 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  花環(huán)... 477
訓練4  電纜切割... 479
9.2  深度優(yōu)先搜索... 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 剪枝優(yōu)化... 517
訓練1  數(shù)獨游戲... 518
訓練2  生日蛋糕... 521
訓練3  木棒... 522
9.3  廣度優(yōu)先搜索... 524
9.3.1  分支限界法... 525
9.3.2  隊列式廣度優(yōu)先搜索.... 525
9.3.3  優(yōu)先隊列式廣度優(yōu)先搜索... 535
訓練1  迷宮問題... 541
訓練2  加滿油箱... 542
9.3.4  嵌套廣度優(yōu)先搜索... 545
訓練  推箱子... 545
9.3.5  雙向廣度優(yōu)先搜索... 549
訓練  魔鬼Ⅱ... 549
9.4  啟發(fā)式搜索... 551
9.4.1  A*算法... 552
9.4.2  IDA*算法... 552
訓練1  八數(shù)碼... 552
訓練2  八數(shù)碼II 562
訓練3  第K短路... 565
訓練4  冪運算... 567