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

李峰，本碩均就讀於西北工業大學計算機學院，曾在韓國成均館大學交流半年，CSDN博客專家，現就職於騰訊科技有限公司任高級工程師，工作期間，技術成果豐碩，多次獲獎。

目錄
第1章算法之美1
1.1生活中的算法——猜數遊戲1
1.1.1好玩的猜數遊戲2
1.1.2遊戲的秘密——二分搜索技術2
1.1.3猜數遊戲算法實現4
1.2算法的指標——空間複雜度和時間複雜度6
1.2.1時間複雜度6
1.2.2空間複雜度9
1.3經典算法回顧——排序算法10
1.3.1冒泡排序10
1.3.2簡單選擇排序14
1.3.3直接插入排序19
1.4怎樣才能學好算法23

第2章貪心算法24
2.1短淺的眼光——貪心24
2.1.1適當的貪心——壞事變好事25
2.1.2過度貪心——賠了夫人又折兵25
2.1.3為貪心加上限制25
2.2美麗心靈——哈夫曼編碼26
2.2.1認識哈夫曼編碼26
2.2.2如何設計哈夫曼編碼27
2.2.3哈夫曼編碼算法實現33
2.3帶你去旅行——單源最短路徑36
2.3.1如何最快到朋友家做客36
2.3.2從最短的第一條路開始分析37
2.3.3找到抵達朋友家的最短路徑38
2.3.4Dijkstra算法實現44
2.4選擇困難症——背包問題46
2.4.1如何裝沙子賺更多的錢47
2.4.2海盜的智慧47
2.4.3背包問題算法實現50
2.5搬家師傅的煩惱——集裝箱裝載問題52
2.5.1如何裝更多的物品53
2.5.2搬家師傅的十年經驗53
2.5.3裝載問題算法實現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找出硬幣的規律64
3.3再談排序算法（1）——合併排序66
3.3.1如何將分而治之思想應用到合併排序上67
3.3.2先對一半的數字進行考慮67
3.3.3合併排序算法實現70
3.4再談排序算法（2）——快速排序74
3.4.1如何將分而治之思想應用到快速排序上74
3.4.2找到一個“分”的中心75
3.4.3快速排序算法實現79
3.4.4排序算法總結81
3.5累人的比賽——循環賽日程安排82
3.5.1最公平的比賽82
3.5.2如何設計循環賽83
3.5.3找出循環賽的排列規律86

第4章樹算法89
4.1生活中的“樹”89
4.1.1炎黃子孫，生生不息90
4.1.2學校的組織結構90
4.1.3操作系統的目錄結構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互聯網的連接136
5.2尋找所有的城市——有向圖的遍歷137
5.2.1什麼是有向圖137
5.2.2有向圖的深度優先遍歷138
5.2.3有向圖的廣度優先遍歷144
5.3最短的管道——Kruskal算法149
5.3.1如何鋪設最短的管道149
5.3.2什麼是最小生成樹150
5.3.3Kruskal算法的貪心思想151
5.3.4Kruskal算法實現156
5.4再談最短的管道——Prim算法158
5.4.1基於管道的邊和結點貪心的區別159
5.4.2Prim算法的貪心思想159
5.4.3Prim算法實現162
5.5多源最短路徑——Floyd算法164
5.5.1朋友之間相互訪問的最短路徑164
5.5.2自上而下分析朋友之間的最短路徑165
5.5.3自下而上迭代朋友之間的最短路徑166
5.5.4Floyd算法實現172

第6章動態規划算法176
6.1長遠的眼光——動態規劃176
6.1.1時間倒流，改變歷史177
6.1.2慎用貪心算法177
6.1.3強者恆強，弱者恆弱——最優子結構178
6.2智能的語言翻譯——編輯距離178
6.2.1設計語言翻譯系統179
6.2.2考慮最後一次編輯情況180
6.2.3自下而上進行距離編輯186
6.3智能的電梯——電梯優化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現代計算機的福音——回溯法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剪掉沒有營養的分支279
8.1.3條條大路通羅馬——和回溯法的區別280
8.2再談迷宮中的小老鼠問題281
8.2.1迷宮中的小老鼠問題回顧281
8.2.2使用分支限界思路規劃小老鼠的路徑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