Python算法從入門到實踐

第1章  初步認(rèn)識算法 1
1.1  什么是算法 2
1.1.1  一道有趣的智力題 2
1.1.2  算法的定義 2
1.1.3  計算機(jī)中的算法 3
1.1.4  算法在編程語言中的定義 4
1.2  衡量算法的優(yōu)劣 4
1.2.1  衡量算法優(yōu)劣的標(biāo)準(zhǔn) 4
1.2.2  算法復(fù)雜度 5
1.2.3  時間復(fù)雜度與空間復(fù)雜度的取舍問題 8
第2章  枚舉算法思想 9
2.1  枚舉算法概述 10
2.1.1  枚舉算法介紹 10
2.1.2  Python中的枚舉算法 10
2.2  破解謎題 11
2.2.1  算法分析 11
2.2.2  具體實現(xiàn) 11
2.3  破解24點游戲 12
2.3.1  算法分析 12
2.3.2  使用枚舉算法解決24點問題 13
2.4  解決熄燈問題 16
2.4.1  算法分析 17
2.4.2  使用numpy和枚舉算法解決熄燈問題 19
2.5  解決“討厭的青蛙”問題 20
2.5.1  算法分析 21
2.5.2  具體實現(xiàn) 22
2.6  解決“雞兔同籠”問題 24
2.6.1  算法分析 24
2.6.2  具體實現(xiàn)：輸入頭和腳的個數(shù)的解法 24
2.7  解決“水仙花數(shù)”問題 25
2.7.1  找出1000以內(nèi)的水仙花數(shù) 25
2.7.2  找出5位水仙花數(shù) 26
2.7.3  找出10000以內(nèi)的水仙花數(shù)(包括1位、2位) 26
第3章  遞歸算法思想 29
3.1  遞歸算法思想基礎(chǔ) 30
3.1.1  什么是遞歸 30
3.1.2  對遞歸和循環(huán)的生動解釋 31
3.1.3  用歸納法來理解遞歸 32
3.1.4  遞歸的三個要素 32
3.2  解決“斐波那契數(shù)列”問題 33
3.2.1  算法分析 33
3.2.2  計算斐波那契數(shù)列的第n項值 34
3.2.3  使用Memorization(記憶化)優(yōu)化遞歸 35
3.3  用遞歸算法解決“漢諾塔”問題 36
3.3.1  算法分析 37
3.3.2  使用遞歸算法解決“漢諾塔”問題的具體實現(xiàn) 38
3.4  解決“階乘”問題 40
3.4.1  算法分析 40
3.4.2  使用遞歸算法計算10之內(nèi)的階乘 41
3.4.3  使用循環(huán)計算階乘 41
3.5  進(jìn)制轉(zhuǎn)換器 42
3.5.1  算法分析 42
3.5.2  比較遞歸方案和循環(huán)方案 42
3.6  解決二叉樹遍歷問題 43
3.6.1  算法分析 43
3.6.2  實現(xiàn)樹結(jié)構(gòu) 44
3.6.3  遞歸遍歷方案 45
3.7  求解公約數(shù)和小公倍數(shù) 46
3.7.1  算法分析 47
3.7.2  基于遞歸算法的方案 47
3.8  解決全排列問題 48
3.8.1  具體實現(xiàn)：將全排列問題分解成多個子問題 48
3.8.2  字節(jié)跳動的一道面試題：遞歸實現(xiàn)n的全排列 49
3.9  解決迷宮問題 49
3.9.1  算法分析 50
3.9.2  具體實現(xiàn) 50
第4章  分治算法思想 53
4.1  分治算法思想基礎(chǔ) 54
4.1.1  什么是分治算法 54
4.1.2  分治法的解題思路 54
4.1.3  總結(jié)分治法能解決什么類型的問題 56
4.2  找出有序列表中的值 56
4.2.1  算法分析 56
4.2.2  使用二分法在有序列表中找出指定的值 56
4.2.3  使用分治算法判斷某個元素是否在列表中 57
4.3  求順序表中數(shù)據(jù)的值 58
4.3.1  算法分析 58
4.3.2  具體實現(xiàn) 58
4.4  解決小值和值的問題 59
4.4.1  算法分析 59
4.4.2  查找列表中元素的小值和值 59
4.5  解決第k小(大)元素的問題 61
4.5.1  算法分析 61
4.5.2  找出一組序列中的第k小(大)的元素 61
4.5.3  找出列表中第k大的元素 62
4.6  快速排序 62
4.6.1  算法分析 63
4.6.2  快速排序具體方案 63
4.7  實現(xiàn)歸并排序 63
4.7.1  算法分析 63
4.7.2  對指定列表實現(xiàn)歸并排序 64
4.8  整數(shù)劃分 64
4.8.1  算法分析 65
4.8.2  整數(shù)劃分問題的具體實現(xiàn) 65
4.9  棋盤覆蓋 65
4.9.1  算法分析 66
4.9.2  使用分治算法解決棋盤覆蓋問題 66
4.9.3  GUI版本的解決棋盤覆蓋方案 67
4.10  解決漢諾塔問題 70
4.10.1  算法分析 70
4.10.2  用分治算法解決漢諾塔問題 71
4.11  解決循環(huán)賽問題 72
4.11.1  算法分析 72
4.11.2  根據(jù)輸入的比賽人數(shù)解決循環(huán)賽問題 72
第5章  貪心算法思想 75
5.1  貪心算法思想基礎(chǔ) 76
5.1.1  什么是貪心算法 76
5.1.2  貪心算法的基本思路和基本特性 76
5.2  解決“找零方案”問題 77
5.2.1  算法分析 77
5.2.2  解決“找零方案”的具體實現(xiàn) 77
5.3  解決“汽車加油”問題 78
5.3.1  算法分析 78
5.3.2  計算少加油次數(shù) 79
5.3.3  計算如何加油次數(shù)會少 79
5.4  解決“求子數(shù)組之和”問題 80
5.4.1  算法分析 80
5.4.2  具體實現(xiàn) 81
5.5  解決“幼兒園分糖果”問題 81
5.5.1  算法分析 81
5.5.2  具體實現(xiàn) 82
5.6  圣誕節(jié)的禮物 82
5.6.1  算法分析 83
5.6.2  分配指定箱數(shù)的糖果 83
5.7  解決“活動安排”問題 84
5.7.1  算法分析 85
5.7.2  使用貪心算法解決“活動安排”問題的方案 85
5.8  解決“搖擺序列”問題 86
5.8.1  算法分析 86
5.8.2  具體解決方案 88
5.9  移除k個數(shù)字 89
5.9.1  算法分析 89
5.9.2  具體實現(xiàn)方案 89
5.10  解決“背包”問題 90
5.10.1  算法分析 90
5.10.2  使用小重量貪心策略解決背包問題 90
5.10.3  使用價值密度貪心策略解決背包問題 91
5.10.4  從單位重量價值角度解決背包問題 92
5.11  解決“霍夫曼編碼”問題 94
5.11.1  算法分析 94
5.11.2  使用內(nèi)置庫解決問題 95
5.11.3  實現(xiàn)一個可變長度的編碼問題 97
5.12  解決“Kruskal算法”問題 98
5.12.1  算法分析 98
5.12.2  種使用Kruskal算法獲取小生成樹的方案 100
5.12.3  第二種使用Kruskal算法獲取小生成樹的方案 101
5.12.4  第三種使用Kruskal算法獲取小生成樹的方案 103
5.13  解決Prim算法問題 105
5.13.1  算法分析 105
5.13.2  種方案 106
5.13.3  第二種方案 107
5.14  解決“馬踏棋盤”問題 109
5.14.1  算法分析 109
5.14.2  使用貪心算法和遞歸算法解決“馬踏棋盤”問題 109
第6章  試探算法思想 113
6.1  試探算法思想基礎(chǔ) 114
6.1.1  試探法算法介紹 114
6.1.2  使用回溯算法的步驟 114
6.1.3  回溯算法會影響程序的效率嗎 115
6.2  解決“解空間”問題 115
6.2.1  算法分析 116
6.2.2  使用子集樹模板遞歸創(chuàng)建一個通用模板 116
6.2.3  使用排列樹模板遞歸創(chuàng)建一個通用模板 117
6.3  解決“全排列”問題 118
6.3.1  算法分析 119
6.3.2  實現(xiàn) 'a', 'b', 'c', 'd' 四個元素的全排列 119
6.4  解決“選排列”問題 120
6.4.1  算法分析 120
6.4.2  使用回溯算法解決“選排列”問題 120
6.5  解決“找零錢”問題 122
6.5.1  算法分析 122
6.5.2  使用回溯算法解決“找零錢”問題 123
6.6  解決“長公共子序列”問題 124
6.6.1  算法分析 124
6.6.2  使用回溯算法解決長公共子序列問題 125
6.7  解決“排課”問題 126
6.7.1  算法分析 127
6.7.2  使用回溯算法解決排課問題 127
6.8  解決“作業(yè)調(diào)度”問題 129
6.8.1  算法分析 129
6.8.2  使用回溯算法解決作業(yè)調(diào)度問題 130
6.9  解決“圖的遍歷”問題 131
6.9.1  算法分析 132
6.9.2  具體實現(xiàn) 132
6.10  解決“爬樓梯”問題 133
6.10.1  算法分析 133
6.10.2  具體實現(xiàn) 133
6.11  解決“m-著色”問題 134
6.11.1  算法分析 135
6.11.2  具體實現(xiàn) 135
6.12  解決“取物搭配”問題 137
6.12.1  算法分析 137
6.12.2  使用回溯算法解決“取物搭配”問題 137
6.13  解決“旅行商”問題 139
6.13.1  算法分析 139
6.13.2  具體實現(xiàn) 139
6.14  解決“0-1背包”問題 141
6.14.1  算法分析 141
6.14.2  使用回溯子集樹法解決問題 141
6.15  解決“野人與傳教士”問題 142
6.15.1  算法分析 143
6.15.2  使用回溯子集樹法解決野人與傳教士問題 143
6.16  解決“騎士巡邏”問題 144
6.16.1  算法分析 145
6.16.2  使用試探算法解決“騎士巡邏”問題 145
6.17  解決“八皇后”問題的4種方案 147
6.17.1  算法分析 147
6.17.2  使用回溯法解決八皇后問題 147
6.17.3  使用遞歸回溯算法解決八皇后問題 148
6.17.4  在縱向和斜向判斷是否存在其他皇后 151
6.18  解決“迷宮”問題 154
6.18.1  算法分析 154
6.18.2  使用回溯法解決迷宮問題 154
6.19  解決面試題“矩陣中的路徑” 156
6.19.1  算法分析 157
6.19.2  具體實現(xiàn) 157
6.20  解決“馬踏棋盤”問題 158
6.20.1  算法分析 159
6.20.2  使用回溯算法解決“5×5馬踏棋盤”問題 159
第7章  迭代算法思想 161
7.1  迭代算法思想基礎(chǔ) 162
7.1.1  迭代算法思想介紹 162
7.1.2  迭代法和方程 162
7.2  解決“斐波那契數(shù)列”問題 163
7.2.1  算法分析 163
7.2.2  使用迭代算法計算第12個月時兔子的數(shù)量 164
7.2.3  比較迭代算法和遞歸算法的效率 164
7.3  解決“角谷猜想”問題 165
7.3.1  算法分析 165
7.3.2  種方案 165
7.3.3  第二種方案 166
7.4  使用牛頓迭代法計算方程的根 167
7.4.1  算法分析 167
7.4.2  計算方程x3-x-1=0的根 167
7.4.3  比較簡單迭代法和牛頓迭代法 168
7.5  使用牛頓迭代法求極值 172
7.5.1  算法分析 172
7.5.2  具體實現(xiàn) 172
7.6  求平方根 173
7.6.1  算法分析 173
7.6.2  使用牛頓迭代法求平方根 173
7.7  求極值并繪制曲線 175
7.7.1  算法分析 175
7.7.2  使用牛頓迭代法求極值并繪制曲線 175
7.8  求解輸入的方程 177
7.8.1  項目需求 178
7.8.2  使用牛頓迭代法求解輸入的方程 178
7.9  求x附近的一個實根 179
7.9.1  算法分析 179
7.9.2  求方程在x附近的一個實根 179
7.10  解決“非線性方程組”問題 180
7.10.1  使用內(nèi)置函數(shù)求解非線性方程組 180
7.10.2  使用第三方庫函數(shù)求解非線性方程組 181
7.11  求解線性方程組 182
7.11.1  算法分析 183
7.11.2  使用雅克比迭代法求解線性方程組 183
7.12  使用Gauss-Seidel迭代法求解線性方程組 185
7.12.1  算法分析 185
7.12.2  具體實現(xiàn) 185
7.13  解決數(shù)值分析問題 187
7.13.1  使用迭代法求解方程 187
7.13.2  解決“龍貝格求積公式”問題 192
7.13.3  解決“三次樣條插值”問題 193
7.13.4  解決“拉格朗日插值公式”問題 196
第8章  查找算法 199
8.1  什么是查找算法 200
8.2  線性表查找：順序查找 200
8.2.1  順序查找法基礎(chǔ) 201
8.2.2  順序查找的時間復(fù)雜度 201
8.2.3  算法演練——實現(xiàn)順序查找算法 202
8.2.4  算法演練——實現(xiàn)有序列表查找 202
8.2.5  算法演練——實現(xiàn)無序列表查找 203
8.2.6  算法演練——在列表中查找x是否存在 203
8.3  線性表查找：折半查找算法 204
8.3.1  折半查找算法基礎(chǔ) 204
8.3.2  算法演練——使用折半查找算法查找數(shù)據(jù) 205
8.3.3  算法演練——使用折半查找算法查找指定數(shù)字 205
8.3.4  算法演練——使用遞歸法實現(xiàn)折半查找算法 206
8.3.5  算法演練——比較順序查找和折半查找 206
8.4  線性表查找：插值查找算法 208
8.4.1  插值查找算法基礎(chǔ) 208
8.4.2  算法演練——使用插值查找法查找指定的數(shù)據(jù) 208
8.5  線性表查找：分塊查找算法 209
8.5.1  分塊查找算法基礎(chǔ) 209
8.5.2  算法演練——使用分塊查找算法在列表中查找某元素 211
8.5.3  算法演練——改進(jìn)的使用分塊查找算法 212
8.6  基于樹的查找法：二叉排序樹算法 213
8.6.1  二叉排序樹算法基礎(chǔ) 214
8.6.2  插入和生成 214
8.6.3  刪除操作 215
8.6.4  查找操作 217
8.6.5  算法演練——實現(xiàn)二叉樹的搜索、插入、刪除、先序遍歷、中序遍歷和后序遍歷操作 217
8.7  基于樹的查找法：平衡二叉排序樹算法 220
8.7.1  平衡二叉排序樹算法基礎(chǔ) 220
8.7.2  Python判斷平衡二叉樹的方法 223
8.7.3  算法演練——實現(xiàn)平衡二叉樹的基本操作 223
8.8  哈希查找算法 229
8.8.1  哈希算法的基本思想 230
8.8.2  構(gòu)造哈希函數(shù) 230
8.8.3  處理沖突 232
8.8.4  哈希表的查找過程 234
8.8.5  算法演練——使用哈希算法查找數(shù)據(jù) 234
8.9  斐波那契查找算法 235
8.9.1  斐波那契查找算法基礎(chǔ) 235
8.9.2  算法演練——使用斐波那契查找算法查找數(shù)據(jù) 236
8.9.3  算法演練——比較順序查找、二分查找、插值查找和斐波那契查找 237
8.10  紅黑樹查找算法 239
8.10.1  紅黑樹查找算法基礎(chǔ) 239
8.10.2  算法演練——使用紅黑樹操作數(shù)據(jù) 240
8.10.3  算法演練——繪制紅黑樹的插入圖 244
第9章  排序算法 249
9.1  什么是排序算法 250
9.1.1  排序算法的定義 250
9.1.2  排序算法的分類 250
9.2  插入排序算法 250
9.2.1  插入排序算法基礎(chǔ) 251
9.2.2  直接插入排序算法 251
9.2.3  算法演練——排序一個列表 252
9.2.4  算法演練——升序和降序排列 253
9.3  希爾排序 254
9.3.1  希爾排序算法基礎(chǔ) 254
9.3.2  算法演練——使用希爾排序算法對數(shù)據(jù)進(jìn)行排序處理 255
9.3.3  算法演練——排序一個列表 256
9.3.4  算法演練——使用希爾排序算法對列表進(jìn)行排序 257
9.4  交換類排序：冒泡排序算法 258
9.4.1  冒泡排序(相鄰比序法)算法基礎(chǔ) 258
9.4.2  算法演練——簡單的冒泡排序 259
9.4.3  算法演練——實現(xiàn)從大到小的冒泡排序 260
9.4.4  算法演練——使用冒泡排序算法的優(yōu)化 261
9.5  交換類排序：快速排序算法 263
9.5.1  快速排序算法基礎(chǔ) 264
9.5.2  算法演練——實現(xiàn)基本的快速排列 265
9.5.3  算法演練——使用快速排序算法排列一個列表 266
9.6  選擇排序算法 267
9.6.1  直接選擇排序算法基礎(chǔ) 267
9.6.2  樹形選擇排序算法基礎(chǔ) 268
9.6.3  算法演練——使用直接選擇排序算法 268
9.6.4  算法演練——使用直接選擇排序算法排列一個列表 269
9.7  堆排序算法 270
9.7.1  堆排序算法基礎(chǔ) 270
9.7.2  算法演練——使用堆排序處理數(shù)據(jù) 272
9.7.3  算法演練——實現(xiàn)堆排序 273
9.8  歸并排序算法 276
9.8.1  歸并排序算法基礎(chǔ) 276
9.8.2  兩路歸并算法的思路 277
9.8.3  實現(xiàn)歸并排序 278
9.8.4  算法演練——使用歸并排序算法排列一個列表 279
9.8.5  算法演練——圖解歸并排序算法 280
9.9  基數(shù)排序算法 282
9.9.1  多關(guān)鍵字排序 282
9.9.2  鏈?zhǔn)交鶖?shù)排序 283
9.9.3  算法演練——使用基數(shù)排序算法排序隨機(jī)數(shù)字 284
9.9.4  算法演練——使用基數(shù)排序算法排序列表 285
9.10  綜合比較各種排序方法 287
第10章  使用算法解決數(shù)據(jù)結(jié)構(gòu)問題 289
10.1  約瑟夫環(huán) 290
10.1.1  問題描述 290
10.1.2  算法分析 290
10.1.3  具體實現(xiàn) 291
10.2  操作順序表 292
10.2.1  算法分析 293
10.2.2  具體實現(xiàn) 293
10.3  操作鏈表 295
10.3.1  算法分析 295
10.3.2  具體實現(xiàn) 295
10.4  帶有尾節(jié)點引用的單鏈表 297
10.4.1  算法分析 297
10.4.2  具體實現(xiàn) 297
10.5  操作隊列、鏈表、順序表和循環(huán)順序表 299
10.5.1  時間復(fù)雜度分析 299
10.5.2  具體實現(xiàn) 299
10.6  使用多叉樹尋找短路徑 302
10.6.1  算法分析 302
10.6.2  具體實現(xiàn) 302
10.7  樹操作 304
10.7.1  實現(xiàn)AVL樹 304
10.7.2  使用二維數(shù)組生成有向圖 307
10.7.3  使用廣度優(yōu)先和深度優(yōu)先遍歷二叉樹 308
第11章  解決數(shù)學(xué)問題 311
11.1  一段神奇的字符 312
11.1.1  問題描述 312
11.1.2  具體實現(xiàn) 312
11.2  1000以內(nèi)的完全數(shù) 313
11.2.1  問題描述 313
11.2.2  算法分析 314
11.2.3  具體實現(xiàn) 315
11.3  多進(jìn)程驗證哥德巴赫猜想 315
11.3.1  問題描述 315
11.3.2  算法分析 315
11.3.3  具體實現(xiàn) 316
11.4  公約數(shù)和小公倍數(shù) 318
11.4.1  算法分析 318
11.4.2  具體實現(xiàn) 318
11.5  親密數(shù) 319
11.5.1  算法分析 319
11.5.2  具體實現(xiàn) 319
11.6  計算10000以內(nèi)的自守數(shù) 320
11.6.1  算法分析 320
11.6.2  具體實現(xiàn) 320
11.7  矩陣運(yùn)算 320
11.7.1  算法分析 321
11.7.2  具體實現(xiàn) 321
11.8  一元多項式運(yùn)算 322
11.8.1  一元多項式求導(dǎo) 322
11.8.2  實現(xiàn)多項式的加、減、乘法運(yùn)算 323
11.9  素數(shù)問題 325
11.9.1  求1000以內(nèi)的所有素數(shù) 325
11.9.2  孿生素數(shù)問題 326
11.9.3  金蟬素數(shù) 327
11.9.4  可逆素數(shù) 328
11.9.5  回文素數(shù) 329
11.9.6  等差素數(shù)數(shù)列 329
第12章  常見的經(jīng)典算法問題 333
12.1  借書方案 334
12.1.1  算法分析 334
12.1.2  具體實現(xiàn) 334
12.2  捕魚和分魚 335
12.2.1  算法分析 336
12.2.2  具體實現(xiàn) 336
12.3  出售金魚 336
12.3.1  算法分析 336
12.3.2  具體實現(xiàn) 337
12.4  平分七筐魚 337
12.4.1  算法分析 337
12.4.2  具體實現(xiàn) 338
12.5  繩子的長度和井深 338
12.5.1  算法分析 339
12.5.2  具體實現(xiàn) 339
12.6  雞兔同籠 340
12.6.1  算法分析 340
12.6.2  具體實現(xiàn) 340
12.7  三色球問題 341
12.7.1  算法分析 341
12.7.2  具體實現(xiàn) 342
12.8  計算年齡 342
12.8.1  算法分析 342
12.8.2  具體實現(xiàn) 342
12.9  常勝將軍問題 343
12.9.1  算法分析 344
12.9.2  具體實現(xiàn) 344
12.10  野人與傳教士問題 345
12.10.1  算法分析 345
12.10.2  具體實現(xiàn) 345
12.11  三色旗問題 347
12.11.1  算法分析 347
12.11.2  具體實現(xiàn) 347
12.12  猴子分桃 348
12.12.1  算法分析 348
12.12.2  具體實現(xiàn) 349
第13章  常用的人工智能算法 351
13.1  線性回歸算法 352
13.1.1  線性回歸介紹 352
13.1.2  繪制三維平面 352
13.1.3  預(yù)測房價 353
13.2  二元決策樹算法 359
13.2.1  何為二元決策樹 359
13.2.2  選擇二元決策樹切割點 359
13.2.3  使用二元決策樹擬合數(shù)據(jù) 361
13.2.4  確定深度的算法 362
13.3  Bagging算法 365
13.3.1  何為Bagging算法 365
13.3.2  實現(xiàn)Bootstrap采樣 366
13.4  Boosting算法 367
13.4.1  Boosting基礎(chǔ) 367
13.4.2  心絞痛ROC曲線檢測系統(tǒng) 368
13.5  隨機(jī)森林算法 372
13.5.1  什么是隨機(jī)森林 373
13.5.2  分析聲吶數(shù)據(jù) 373