從零開始學(xué)算法（基于Python）

目錄
第1章算法之美1
1.1生活中的算法——猜數(shù)游戲1
1.1.1好玩的猜數(shù)游戲2
1.1.2游戲的秘密——二分搜索技術(shù)2
1.1.3猜數(shù)游戲算法實(shí)現(xiàn)4
1.2算法的指標(biāo)——空間復(fù)雜度和時(shí)間復(fù)雜度6
1.2.1時(shí)間復(fù)雜度6
1.2.2空間復(fù)雜度9
1.3經(jīng)典算法回顧——排序算法10
1.3.1冒泡排序10
1.3.2簡單選擇排序14
1.3.3直接插入排序19
1.4怎樣才能學(xué)好算法23
第2章貪心算法24
2.1短淺的眼光——貪心24
2.1.1適當(dāng)?shù)呢澬摹獕氖伦兒檬?5
2.1.2過度貪心——賠了夫人又折兵25
2.1.3為貪心加上限制25
2.2美麗心靈——哈夫曼編碼26
2.2.1認(rèn)識(shí)哈夫曼編碼26
2.2.2如何設(shè)計(jì)哈夫曼編碼27
2.2.3哈夫曼編碼算法實(shí)現(xiàn)33
2.3帶你去旅行——單源最短路徑36
2.3.1如何最快到朋友家做客36
2.3.2從最短的第一條路開始分析37
2.3.3找到抵達(dá)朋友家的最短路徑38
2.3.4Dijkstra算法實(shí)現(xiàn)44
2.4選擇困難癥——背包問題46
2.4.1如何裝沙子賺更多的錢47
2.4.2海盜的智慧47
2.4.3背包問題算法實(shí)現(xiàn)50
2.5搬家?guī)煾档臒馈b箱裝載問題52
2.5.1如何裝更多的物品53
2.5.2搬家?guī)煾档氖杲?jīng)驗(yàn)53
2.5.3裝載問題算法實(shí)現(xiàn)55
第3章分而治之算法58
3.1縱橫捭闔，各個(gè)擊破——分而治之58
3.1.1分而治之——把復(fù)雜的事情簡單化59
3.1.2可分可治，缺一不可59
3.1.3合久必分，分久必合——治而合之60
3.2真幣和假幣——偽幣問題61
3.2.1可惡的假幣62
3.2.2先對一半的硬幣進(jìn)行考慮62
3.2.3找出硬幣的規(guī)律64
3.3再談排序算法（1）——合并排序66
3.3.1如何將分而治之思想應(yīng)用到合并排序上67
3.3.2先對一半的數(shù)字進(jìn)行考慮67
3.3.3合并排序算法實(shí)現(xiàn)70
3.4再談排序算法（2）——快速排序74
3.4.1如何將分而治之思想應(yīng)用到快速排序上74
3.4.2找到一個(gè)“分”的中心75
3.4.3快速排序算法實(shí)現(xiàn)79
3.4.4排序算法總結(jié)81
3.5累人的比賽——循環(huán)賽日程安排82
3.5.1最公平的比賽82
3.5.2如何設(shè)計(jì)循環(huán)賽83
3.5.3找出循環(huán)賽的排列規(guī)律86
第4章樹算法89
4.1生活中的“樹”89
4.1.1炎黃子孫，生生不息90
4.1.2學(xué)校的組織結(jié)構(gòu)90
4.1.3操作系統(tǒng)的目錄結(jié)構(gòu)91
4.2一葉一菩提——二叉樹的遍歷92
4.2.1什么是二叉樹92
4.2.2二叉樹的前序遍歷92
4.2.3二叉樹的中序遍歷97
4.2.4二叉樹的后序遍歷102
4.2.5二叉樹的平層遍歷107
4.3重建家譜圖——二叉樹的還原111
4.3.1什么是二叉樹的還原112
4.3.2前序遍歷和中序遍歷還原家譜圖113
4.3.3中序遍歷和后序遍歷還原家譜圖118
4.4十年樹木，百年樹人——二叉樹的高度123
4.4.1什么是樹的高度123
4.4.2在樹的遍歷基礎(chǔ)上增加高度信息124
4.4.3遍歷樹獲得高度信息126
4.5尋根溯源——找到所有祖先結(jié)點(diǎn)128
4.5.1什么是樹的祖先128
4.5.2在樹的遍歷基礎(chǔ)上增加結(jié)點(diǎn)找到信息129
4.5.3遍歷樹獲得所有祖先131
第5章圖算法134
5.1生活中的“圖”134
5.1.1城市的交通軌道135
5.1.2人與人之間的關(guān)系136
5.1.3互聯(lián)網(wǎng)的連接136
5.2尋找所有的城市——有向圖的遍歷137
5.2.1什么是有向圖137
5.2.2有向圖的深度優(yōu)先遍歷138
5.2.3有向圖的廣度優(yōu)先遍歷144
5.3最短的管道——Kruskal算法149
5.3.1如何鋪設(shè)最短的管道149
5.3.2什么是最小生成樹150
5.3.3Kruskal算法的貪心思想151
5.3.4Kruskal算法實(shí)現(xiàn)156
5.4再談最短的管道——Prim算法158
5.4.1基于管道的邊和結(jié)點(diǎn)貪心的區(qū)別159
5.4.2Prim算法的貪心思想159
5.4.3Prim算法實(shí)現(xiàn)162
5.5多源最短路徑——Floyd算法164
5.5.1朋友之間相互訪問的最短路徑164
5.5.2自上而下分析朋友之間的最短路徑165
5.5.3自下而上迭代朋友之間的最短路徑166
5.5.4Floyd算法實(shí)現(xiàn)172
第6章動(dòng)態(tài)規(guī)劃算法176
6.1長遠(yuǎn)的眼光——?jiǎng)討B(tài)規(guī)劃176
6.1.1時(shí)間倒流，改變歷史177
6.1.2慎用貪心算法177
6.1.3強(qiáng)者恒強(qiáng)，弱者恒弱——最優(yōu)子結(jié)構(gòu)178
6.2智能的語言翻譯——編輯距離178
6.2.1設(shè)計(jì)語言翻譯系統(tǒng)179
6.2.2考慮最后一次編輯情況180
6.2.3自下而上進(jìn)行距離編輯186
6.3智能的電梯——電梯優(yōu)化196
6.3.1設(shè)計(jì)智能電梯196
6.3.2先考慮最后一次電梯停留的情況197
6.3.3自下而上計(jì)算電梯的停留過程200
6.4名字的相似度——最長公共子序列208
6.4.1外國人名的相似度208
6.4.2考慮最后一個(gè)字符比較情況209
6.4.3自下而上進(jìn)行距離編輯213
第7章回溯法219
7.1現(xiàn)代計(jì)算機(jī)的福音——回溯法220
7.1.1讓猴子打出《莎士比亞全集》220
7.1.2一條路走到黑——深度遍歷221
7.1.3亂花漸欲迷人眼——搜索中的剪枝223
7.2不能攻擊的皇后——8個(gè)皇后問題224
7.2.1一山不容二虎224
7.2.2如何設(shè)計(jì)8個(gè)皇后的解向量226
7.2.3搜索過程中的剪枝228
7.3絕望的小老鼠——迷宮中的小老鼠241
7.3.1上帝視角幫助小老鼠241
7.3.2小老鼠如何進(jìn)行搜索242
7.3.3小老鼠的出逃之路248
7.4再談0/1背包問題253
7.4.1背包問題回顧253
7.4.2還可以使用貪心算法求解嗎253
7.4.3通過搜索求解背包問題255
7.5再談集裝箱裝載問題262
7.5.1集裝箱裝載問題回顧263
7.5.2使用貪心算法求解而存在的問題263
7.5.3通過搜索求解裝載問題264
第8章分支限界法276
8.1一步一個(gè)腳印——分支限界277
8.1.1步步為營——廣度遍歷277
8.1.2剪掉沒有營養(yǎng)的分支279
8.1.3條條大路通羅馬——和回溯法的區(qū)別280
8.2再談迷宮中的小老鼠問題281
8.2.1迷宮中的小老鼠問題回顧281
8.2.2使用分支限界思路規(guī)劃小老鼠的路徑283
8.2.3小老鼠的出逃之路287
8.3三談0/1背包問題291
8.3.10/1背包問題回顧292
8.3.2使用分支限界的思路裝船294
8.3.3背包的搜索過程300
8.4三談集裝箱裝載問題305
8.4.1集裝箱裝載問題回顧305
8.4.2使用分支限界的思路裝載集裝箱307
8.4.3集裝箱的裝載過程314