Python常用算法手冊(cè)

第 1 章  初步認(rèn)識(shí)算法思想
1.1 什么是算法 ........................................................................................................1
1.1.1 一道趣味題 .........................................................................................................1
1.1.2 算法的定義 .........................................................................................................2
1.1.3 計(jì)算機(jī)中的算法 .................................................................................................2
1.1.4 總結(jié)算法的特征 .................................................................................................3
1.2 算法是程序的靈魂 ............................................................................................3
1.3 算法的表示方法 ................................................................................................4
1.3.1 用流程圖來表示算法 .........................................................................................4
1.3.2 用 N-S 流程圖來表示算法.................................................................................5
1.4 Python 算法思想 ................................................................................................6
1.4.1 常用的算法思想 .................................................................................................6
1.4.2 衡量算法優(yōu)劣的標(biāo)準(zhǔn) .........................................................................................6
1.4.3 算法復(fù)雜度 .........................................................................................................7
1.4.4 時(shí)間復(fù)雜度與空間復(fù)雜度的取舍問題 .............................................................9
1.5 小結(jié) ..................................................................................................................10
第 2 章  枚舉算法思想
2.1 枚舉算法基礎(chǔ) .................................................................................................. 11
2.1.1 枚舉算法介紹 ...................................................................................................11
2.1.2 Python 中枚舉算法的實(shí)現(xiàn)思路.......................................................................11
2.2 算法演練——找出符合條件的 5 位數(shù) ..........................................................12
2.2.1 算法分析：首位數(shù)不能是誰 ...........................................................................12
2.2.2 具體實(shí)現(xiàn) ...........................................................................................................12
2.3 算法演練——24 點(diǎn)游戲 .................................................................................13
2.3.1 算法分析：加括號(hào)和去除重復(fù)表達(dá)式 ...........................................................13
2.3.2 具體實(shí)現(xiàn) ...........................................................................................................14
2.3.3 第二種方案：列表切片操作實(shí)現(xiàn)排列組合 ...................................................17
2.3.4 第三種方案：itertools 模塊實(shí)現(xiàn)排列組合 .....................................................17
2.4 算法演練——解決熄燈問題 ...........................................................................19
2.4.1 算法分析：規(guī)則中的規(guī)律 ...............................................................................20
2.4.2 具體實(shí)現(xiàn) ...........................................................................................................21
2.5 算法演練——解決“討厭的青蛙”問題 .......................................................23
2.5.1 算法分析：縮小解的空間 ...............................................................................24
2.5.2 具體實(shí)現(xiàn) ...........................................................................................................24
2.6 小結(jié) ..................................................................................................................26
第 3 章  遞歸算法思想
3.1 遞歸算法思想基礎(chǔ) ..........................................................................................27
3.2 算法演練——解決“斐波那契數(shù)列”問題 ...................................................28
3.2.1 算法分析：找出兔子增加的規(guī)律 ...................................................................28
3.2.2 具體實(shí)現(xiàn) ...........................................................................................................28
3.3 算法演練——解決“漢諾塔”問題 ...............................................................29
3.3.1 算法分析：情景模擬移動(dòng)過程 .......................................................................29
3.3.2 具體實(shí)現(xiàn) ...........................................................................................................30
3.4 算法演練——解決“階乘”問題 ...................................................................32
3.4.1 算法分析：拆分調(diào)用 .......................................................................................32
3.4.2 具體實(shí)現(xiàn)：顯示 6 以內(nèi)階乘過程 ...................................................................32
3.5 算法演練——進(jìn)制轉(zhuǎn)換器 ...............................................................................33
3.5.1 算法分析：除以 2 獲取余數(shù) ...........................................................................33
3.5.2 具體實(shí)現(xiàn)：輸出十進(jìn)制數(shù)字 10 對(duì)應(yīng)的二進(jìn)制數(shù) .........................................33
3.6 算法演練——分解數(shù)字 ...................................................................................34
3.6.1 算法分析：遞歸除以 10 ..................................................................................34
3.6.2 具體實(shí)現(xiàn)：分解 5 位整數(shù) 12345 ....................................................................34
3.7 算法演練——解決二叉樹遍歷問題 ...............................................................34
3.7.1 算法分析：實(shí)現(xiàn)三種遍歷方式 .......................................................................34
3.7.2 實(shí)現(xiàn)樹的結(jié)構(gòu) ...................................................................................................35
3.7.3 二叉樹遞歸遍歷方案 .......................................................................................36
3.8 算法演練——公約數(shù)和小公倍數(shù) .......................................................38
3.8.1 算法分析：整理計(jì)算流程 ...............................................................................38
3.8.2 基于遞歸算法的方案 .......................................................................................38
3.8.3 比較遞歸和非遞歸方案 ...................................................................................39
3.9 小結(jié) ..................................................................................................................40
第 4 章 分治算法思想
4.1 分治算法思想基礎(chǔ) ..........................................................................................41
4.1.1 分治算法介紹與解題步驟 ...............................................................................41
4.1.2 分治算法的思路 ...............................................................................................41
4.1.3 分治算法能解決什么類型的問題 ...................................................................42
4.2 算法演練——二分法找出有序列表指定值 ...................................................43
4.2.1 算法分析：確定中位數(shù) ...................................................................................43
4.2.2 種方案：先判斷再查詢 ...........................................................................43
4.2.3 第二種方案：判斷某個(gè)元素是否在列表中 ...................................................44
4.2.4 第三種方案：找出有序列表中的指定值 .......................................................45
4.3 算法演練——求順序表中數(shù)據(jù)的值 .......................................................45
4.3.1 算法分析：找出每一個(gè)分組中的值 .......................................................45
4.3.2 具體實(shí)現(xiàn)：找出給定列表 list 中的值 ....................................................46
4.4 算法演練——查找列表中元素的小值和值 .......................................46
4.4.1 算法分析：合理分組 .......................................................................................46
4.4.2 種方案：分組計(jì)算 ...................................................................................47
4.4.3 第二種方案：選擇小元素 ...................................................................48
4.5 算法演練——找出一組序列中的第 k ?。ù螅┑脑?...............................48
4.5.1 算法分析：設(shè)置樞紐元素 ...............................................................................48
4.5.2 種方案：分組比較 ...................................................................................49
4.5.3 第二種方案：快速排序的分治算法 ...............................................................49
4.5.4 第三種方案：分組和排序同時(shí)進(jìn)行 ...............................................................50
4.5.5 第四種方案：生成隨機(jī)校驗(yàn)碼 .......................................................................51
4.6 算法演練——快速排序 ...................................................................................51
4.6.1 算法分析：設(shè)定基準(zhǔn)線并對(duì)比 .......................................................................51
4.6.2 具體實(shí)現(xiàn) ...........................................................................................................52
4.6.3 第二種方案：列表推導(dǎo) ...................................................................................52
4.7 算法演練——實(shí)現(xiàn)歸并排序 ...........................................................................53
4.7.1 算法分析：中間下標(biāo)與值大小分配 ...............................................................53
4.7.2 具體實(shí)現(xiàn)：對(duì)列表 [1,6,12,3,8] 進(jìn)行歸并排序 ..............................................54
4.8 算法演練——整數(shù)劃分 ...................................................................................54
4.8.1 算法分析：梳理遞歸關(guān)系 ...............................................................................55
4.8.2 具體實(shí)現(xiàn) ...........................................................................................................55
4.9小結(jié) ..................................................................................................................56
第 5 章  貪心算法思想
5.1 貪心算法思想基礎(chǔ) ..........................................................................................57
5.1.1 貪心算法介紹 ...................................................................................................57
5.1.2 貪心算法的基本思路 .......................................................................................58
5.2 算法演練——解決“找零方案”問題 ...........................................................58
5.2.1 算法分析：零錢的面額是固定的 ...................................................................58
5.2.2 具體實(shí)現(xiàn) ...........................................................................................................58
5.3 算法演練——解決“汽車加油”問題 ...........................................................59
5.3.1 算法分析：先加油后貪心 ...............................................................................59
5.3.2 具體實(shí)現(xiàn) ...........................................................................................................59
5.4 算法演練——解決“求子元素之和問題”問題 ...................................60
5.4.1 算法分析：確定目前子元素的和是否 ...................................................60
5.4.2 具體實(shí)現(xiàn)：計(jì)算整數(shù)列表 s 的連續(xù)子元素之和 ...................................61
5.5 算法演練——解決“幼兒園分糖果”問題 ...................................................61
5.5.1 算法分析：優(yōu)先從需求因子小的孩子進(jìn)行嘗試 ...........................................61
5.5.2 具體實(shí)現(xiàn) ...........................................................................................................61
5.6 算法演練——圣誕節(jié)的禮物 ...........................................................................62
5.6.1 算法分析：單位價(jià)值 ...............................................................................62
5.6.2 具體實(shí)現(xiàn) ...........................................................................................................63
5.7 算法演練——解決“活動(dòng)安排”問題 ...........................................................64
5.7.1 算法分析：活動(dòng)安排問題的解 ...............................................................64
5.7.2 個(gè)方案：快速排序 ...................................................................................65
5.7.3 第二個(gè)方案：通過冒泡排序同步交換數(shù)據(jù) ...................................................66
5.8 算法演練——解決“搖擺序列”問題 ...........................................................67
5.8.1 算法分析：選擇使得搖擺子序列長度更長的數(shù) ...........................................67
5.8.2 具體實(shí)現(xiàn) ...........................................................................................................68
5.9 算法演練——移除 k 個(gè)數(shù)字 ...........................................................................69
5.9.1 算法分析：從高位向低位遍歷 .......................................................................69
5.9.2 具體實(shí)現(xiàn) ...........................................................................................................70
5.10 算法演練——四種解決“霍夫曼編碼”問題的方案 .................................70
5.10.1 算法分析 .........................................................................................................71
5.10.2 種方案：權(quán)值排序 .................................................................................72
5.10.3 第二種方案：使用 Python 自帶的內(nèi)置庫 heapq .........................................73
5.10.4 第三種方案：使用內(nèi)置統(tǒng)計(jì)函數(shù) .................................................................75
5.10.5 第四種方案：實(shí)現(xiàn)完整樹的隊(duì)列操作 .........................................................76
5.11 算法演練——解決“Kruskal 算法”問題 ...................................................78
5.11.1 算法分析：順序選取權(quán)重邊 .........................................................................79
5.11.2 種方案：判斷根結(jié)點(diǎn)是否相同 .............................................................80
5.11.3 第二種方案：將權(quán)重小的邊加入到小生成樹 .....................................81
5.11.4 第三種方案：基于不相交集實(shí)現(xiàn) .................................................................83
5.12 算法演練——解決“Prim 算法”問題 ........................................................85
5.12.1 算法分析：將結(jié)點(diǎn)分組 .................................................................................86
5.12.2 種方案：選取權(quán)重小的一條邊 .........................................................86
5.12.3 第二種方案：隨機(jī)選取結(jié)點(diǎn) .........................................................................87
5.13 小結(jié) ................................................................................................................89