從零開始學算法（基于Python）

目錄
第1章算法之美1
1.1生活中的算法——猜數(shù)游戲1
1.1.1好玩的猜數(shù)游戲2
1.1.2游戲的秘密——二分搜索技術2
1.1.3猜數(shù)游戲算法實現(xiàn)4
1.2算法的指標——空間復雜度和時間復雜度6
1.2.1時間復雜度6
1.2.2空間復雜度9
1.3經(jīng)典算法回顧——排序算法10
1.3.1冒泡排序10
1.3.2簡單選擇排序14
1.3.3直接插入排序19
1.4怎樣才能學好算法23
第2章貪心算法24
2.1短淺的眼光——貪心24
2.1.1適當?shù)呢澬摹獕氖伦兒檬?5
2.1.2過度貪心——賠了夫人又折兵25
2.1.3為貪心加上限制25
2.2美麗心靈——哈夫曼編碼26
2.2.1認識哈夫曼編碼26
2.2.2如何設計哈夫曼編碼27
2.2.3哈夫曼編碼算法實現(xiàn)33
2.3帶你去旅行——單源最短路徑36
2.3.1如何最快到朋友家做客36
2.3.2從最短的第一條路開始分析37
2.3.3找到抵達朋友家的最短路徑38
2.3.4Dijkstra算法實現(xiàn)44
2.4選擇困難癥——背包問題46
2.4.1如何裝沙子賺更多的錢47
2.4.2海盜的智慧47
2.4.3背包問題算法實現(xiàn)50
2.5搬家?guī)煾档臒馈b箱裝載問題52
2.5.1如何裝更多的物品53
2.5.2搬家?guī)煾档氖杲?jīng)驗53
2.5.3裝載問題算法實現(xiàn)55
第3章分而治之算法58
3.1縱橫捭闔，各個擊破——分而治之58
3.1.1分而治之——把復雜的事情簡單化59
3.1.2可分可治，缺一不可59
3.1.3合久必分，分久必合——治而合之60
3.2真幣和假幣——偽幣問題61
3.2.1可惡的假幣62
3.2.2先對一半的硬幣進行考慮62
3.2.3找出硬幣的規(guī)律64
3.3再談排序算法（1）——合并排序66
3.3.1如何將分而治之思想應用到合并排序上67
3.3.2先對一半的數(shù)字進行考慮67
3.3.3合并排序算法實現(xiàn)70
3.4再談排序算法（2）——快速排序74
3.4.1如何將分而治之思想應用到快速排序上74
3.4.2找到一個“分”的中心75
3.4.3快速排序算法實現(xiàn)79
3.4.4排序算法總結81
3.5累人的比賽——循環(huán)賽日程安排82
3.5.1最公平的比賽82
3.5.2如何設計循環(huán)賽83
3.5.3找出循環(huán)賽的排列規(guī)律86
第4章樹算法89
4.1生活中的“樹”89
4.1.1炎黃子孫，生生不息90
4.1.2學校的組織結構90
4.1.3操作系統(tǒng)的目錄結構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在樹的遍歷基礎上增加高度信息124
4.4.3遍歷樹獲得高度信息126
4.5尋根溯源——找到所有祖先結點128
4.5.1什么是樹的祖先128
4.5.2在樹的遍歷基礎上增加結點找到信息129
4.5.3遍歷樹獲得所有祖先131
第5章圖算法134
5.1生活中的“圖”134
5.1.1城市的交通軌道135
5.1.2人與人之間的關系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如何鋪設最短的管道149
5.3.2什么是最小生成樹150
5.3.3Kruskal算法的貪心思想151
5.3.4Kruskal算法實現(xiàn)156
5.4再談最短的管道——Prim算法158
5.4.1基于管道的邊和結點貪心的區(qū)別159
5.4.2Prim算法的貪心思想159
5.4.3Prim算法實現(xiàn)162
5.5多源最短路徑——Floyd算法164
5.5.1朋友之間相互訪問的最短路徑164
5.5.2自上而下分析朋友之間的最短路徑165
5.5.3自下而上迭代朋友之間的最短路徑166
5.5.4Floyd算法實現(xiàn)172
第6章動態(tài)規(guī)劃算法176
6.1長遠的眼光——動態(tài)規(guī)劃176
6.1.1時間倒流，改變歷史177
6.1.2慎用貪心算法177
6.1.3強者恒強，弱者恒弱——最優(yōu)子結構178
6.2智能的語言翻譯——編輯距離178
6.2.1設計語言翻譯系統(tǒng)179
6.2.2考慮最后一次編輯情況180
6.2.3自下而上進行距離編輯186
6.3智能的電梯——電梯優(yōu)化196
6.3.1設計智能電梯196
6.3.2先考慮最后一次電梯停留的情況197
6.3.3自下而上計算電梯的停留過程200
6.4名字的相似度——最長公共子序列208
6.4.1外國人名的相似度208
6.4.2考慮最后一個字符比較情況209
6.4.3自下而上進行距離編輯213
第7章回溯法219
7.1現(xiàn)代計算機的福音——回溯法220
7.1.1讓猴子打出《莎士比亞全集》220
7.1.2一條路走到黑——深度遍歷221
7.1.3亂花漸欲迷人眼——搜索中的剪枝223
7.2不能攻擊的皇后——8個皇后問題224
7.2.1一山不容二虎224
7.2.2如何設計8個皇后的解向量226
7.2.3搜索過程中的剪枝228
7.3絕望的小老鼠——迷宮中的小老鼠241
7.3.1上帝視角幫助小老鼠241
7.3.2小老鼠如何進行搜索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一步一個腳印——分支限界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