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

第1章  語言基礎(chǔ)... 1
1.1  開啟算法之旅：hello world! 1
1.2  常見數(shù)據(jù)類型及其表達(dá)范圍... 2
1.3  玩轉(zhuǎn)輸入輸出... 2
1.4  人生就是不斷地選擇：if…else. 9
1.5  每天都有很多次重復(fù)：for/while. 13
1.6  如何輕松寫一個函數(shù)... 20
1.7  從前有座山，山里有座廟：遞歸之法... 25
1.8  信息攜帶者：定義一個結(jié)構(gòu)體... 29
1.9  巧用數(shù)組——好玩貪吃蛇... 31
1.10  玩轉(zhuǎn)字符串——不一樣的風(fēng)格... 37
 
第2章  算法入門... 42
2.1  算法之美... 42
2.1.1  如何評價一個算法的優(yōu)劣... 42
2.1.2  算法復(fù)雜度的計算方法... 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應(yīng)用... 65
2.4.1  vector 65
訓(xùn)練  間諜... 67
2.4.2  棧... 68
訓(xùn)練  Web導(dǎo)航... 69
2.4.3  queue. 75
訓(xùn)練  騎士移動... 75
2.4.4  list 77
訓(xùn)練  士兵隊列訓(xùn)練... 78
2.4.5  deque. 79
訓(xùn)練  度度熊學(xué)隊列... 80
2.4.6  priority_queue. 82
訓(xùn)練  黑盒子... 83
2.4.7  bitset 85
訓(xùn)練  集合運(yùn)算... 88
2.4.8  set/multiset 90
訓(xùn)練1  集合合并... 91
訓(xùn)練2  并行處理... 92
2.4.9  map/multimap. 94
訓(xùn)練1  硬木種類... 96
訓(xùn)練2  雙重隊列... 97
訓(xùn)練3  水果... 99
2.4.10  STL的常用函數(shù)... 100
訓(xùn)練1  差的中位數(shù)... 106
訓(xùn)練2  中位數(shù)... 108
訓(xùn)練3  訂單管理... 109
訓(xùn)練4  字謎... 110
 
第3章  線性表的應(yīng)用... 112
3.1  順序表... 112
3.2  單鏈表... 116
3.3  雙向鏈表... 119
3.4  循環(huán)鏈表... 122
3.5  靜態(tài)鏈表... 123
訓(xùn)練1  區(qū)塊世界... 126
訓(xùn)練2  悲劇文本... 132
訓(xùn)練3  移動盒子... 133
 
第4章  棧和隊列的應(yīng)用... 140
4.1  順序棧... 140
4.2  鏈棧... 143
4.3  順序隊列... 146
4.4  鏈隊列... 155
訓(xùn)練1  括號匹配... 158
訓(xùn)練2  鐵軌... 160
訓(xùn)練3  矩陣連乘... 164
訓(xùn)練4  打印隊列... 168
訓(xùn)練5  并發(fā)模擬器... 171
 
第5章  樹的應(yīng)用... 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é)構(gòu)... 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
訓(xùn)練1  新二叉樹... 228
訓(xùn)練2  還原樹... 229
訓(xùn)練3  樹... 230
5.4  哈夫曼樹... 232
原理  哈夫曼編碼... 232
訓(xùn)練1  圍欄修復(fù)... 245
訓(xùn)練2  信息熵... 246
訓(xùn)練3  轉(zhuǎn)換哈夫曼編碼... 248
訓(xùn)練4  可變基哈夫曼編碼... 251
 
第6章  圖論基礎(chǔ)... 256
6.1  圖的存儲... 257
6.1.1  鄰接矩陣... 257
6.1.2  邊集數(shù)組... 263
6.1.3  鄰接表... 263
6.1.4  鏈?zhǔn)角跋蛐?.. 271
訓(xùn)練1  的節(jié)點... 274
訓(xùn)練2  有向圖D和E. 276
訓(xùn)練3  奶牛排序... 278
6.2  圖的遍歷... 279
6.2.1  廣度優(yōu)先遍歷... 279
6.2.2  深度優(yōu)先遍歷... 283
訓(xùn)練1  油田... 287
訓(xùn)練2  理想路徑... 290
訓(xùn)練3  騎士的旅程... 293
訓(xùn)練4  抓住那頭牛... 295
6.3  圖的連通性... 298
6.3.1  連通性的相關(guān)知識... 298
6.3.2  Tarjan算法... 302
訓(xùn)練1  電話網(wǎng)絡(luò)... 306
訓(xùn)練2  道路建設(shè)... 308
訓(xùn)練3  圖的底部... 311
訓(xùn)練4  校園網(wǎng)絡(luò)... 313
 
第7章  圖的應(yīng)用... 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
訓(xùn)練1  重型運(yùn)輸... 329
訓(xùn)練2  貨幣兌換... 331
訓(xùn)練3  蟲洞... 332
訓(xùn)練4  短路徑... 335
7.2  小生成樹... 336
7.2.1  Prim算法... 337
7.2.2  Kruskal算法... 346
訓(xùn)練1  叢林之路... 351
訓(xùn)練2  聯(lián)網(wǎng)... 352
訓(xùn)練3  空間站... 354
訓(xùn)練4  道路建設(shè)... 356
7.3  拓?fù)渑判?.. 358
原理  拓?fù)渑判?.. 358
訓(xùn)練1  家族樹... 362
訓(xùn)練2  全排序... 364
訓(xùn)練3  標(biāo)簽球... 366
訓(xùn)練4  秩序... 369
7.4  關(guān)鍵路徑... 371
原理  關(guān)鍵路徑... 371
訓(xùn)練1  關(guān)鍵路徑... 380
訓(xùn)練2  指令安排... 382
訓(xùn)練3  家務(wù)瑣事... 384
訓(xùn)練4  免費DIY之旅... 385
訓(xùn)練5  游戲玩家... 388
 
第8章  查找算法... 391
8.1  哈希表... 391
8.1.1  散列函數(shù)... 392
8.1.2  處理沖突的方法... 394
8.1.3  散列查找及性能分析... 404
訓(xùn)練1  雪花... 406
訓(xùn)練2  公式... 407
訓(xùn)練3  正方形... 409
8.2  字符串模式匹配... 411
8.2.1  BF算法... 412
8.2.2  KMP算法... 415
訓(xùn)練1  統(tǒng)計單詞數(shù)... 421
訓(xùn)練2  KMP字符串匹配... 423
8.3  二叉查找樹... 424
原理  二叉查找樹詳解... 424
訓(xùn)練1  落葉... 436
訓(xùn)練2  完全二叉搜索樹... 439
訓(xùn)練3  硬木種類... 441
訓(xùn)練4  二叉搜索樹... 442
8.4  平衡二叉樹... 444
原理  AVL樹詳解... 445
訓(xùn)練1  平衡二叉樹... 458
訓(xùn)練2  雙重隊列... 461
訓(xùn)練3  黑盒子... 464
訓(xùn)練4  硬木種類... 465
 
第9章  搜索技術(shù)... 466
9.1  二分搜索... 466
原理  二分搜索技術(shù)... 466
訓(xùn)練1  跳房子游戲... 471
訓(xùn)練2  烘干衣服... 475
訓(xùn)練3  花環(huán)... 477
訓(xùn)練4  電纜切割... 479
9.2  深度優(yōu)先搜索... 480
9.2.1  回溯法... 480
9.2.2  子集樹... 483
9.2.3  m叉樹... 491
9.2.4  排列樹... 499
訓(xùn)練1  魅力手鐲... 515
訓(xùn)練2  圖的m著色問題... 516
訓(xùn)練3  N皇后問題... 517
9.2.5  DFS 剪枝優(yōu)化... 517
訓(xùn)練1  數(shù)獨游戲... 518
訓(xùn)練2  生日蛋糕... 521
訓(xùn)練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
訓(xùn)練1  迷宮問題... 541
訓(xùn)練2  加滿油箱... 542
9.3.4  嵌套廣度優(yōu)先搜索... 545
訓(xùn)練  推箱子... 545
9.3.5  雙向廣度優(yōu)先搜索... 549
訓(xùn)練  魔鬼Ⅱ... 549
9.4  啟發(fā)式搜索... 551
9.4.1  A*算法... 552
9.4.2  IDA*算法... 552
訓(xùn)練1  八數(shù)碼... 552
訓(xùn)練2  八數(shù)碼II 562
訓(xùn)練3  第K短路... 565
訓(xùn)練4  冪運(yùn)算... 567