Python常用算法手册

第 1 章  初步认识算法思想
1.1 什么是算法 ........................................................................................................1
1.1.1 一道趣味题 .........................................................................................................1
1.1.2 算法的定义 .........................................................................................................2
1.1.3 计算机中的算法 .................................................................................................2
1.1.4 总结算法的特征 .................................................................................................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 衡量算法优劣的标准 .........................................................................................6
1.4.3 算法复杂度 .........................................................................................................7
1.4.4 时间复杂度与空间复杂度的取舍问题 .............................................................9
1.5 小结 ..................................................................................................................10
第 2 章  枚举算法思想
2.1 枚举算法基础 .................................................................................................. 11
2.1.1 枚举算法介绍 ...................................................................................................11
2.1.2 Python 中枚举算法的实现思路.......................................................................11
2.2 算法演练——找出符合条件的 5 位数 ..........................................................12
2.2.1 算法分析：首位数不能是谁 ...........................................................................12
2.2.2 具体实现 ...........................................................................................................12
2.3 算法演练——24 点游戏 .................................................................................13
2.3.1 算法分析：加括号和去除重复表达式 ...........................................................13
2.3.2 具体实现 ...........................................................................................................14
2.3.3 第二种方案：列表切片操作实现排列组合 ...................................................17
2.3.4 第三种方案：itertools 模块实现排列组合 .....................................................17
2.4 算法演练——解决熄灯问题 ...........................................................................19
2.4.1 算法分析：规则中的规律 ...............................................................................20
2.4.2 具体实现 ...........................................................................................................21
2.5 算法演练——解决“讨厌的青蛙”问题 .......................................................23
2.5.1 算法分析：缩小解的空间 ...............................................................................24
2.5.2 具体实现 ...........................................................................................................24
2.6 小结 ..................................................................................................................26
第 3 章  递归算法思想
3.1 递归算法思想基础 ..........................................................................................27
3.2 算法演练——解决“斐波那契数列”问题 ...................................................28
3.2.1 算法分析：找出兔子增加的规律 ...................................................................28
3.2.2 具体实现 ...........................................................................................................28
3.3 算法演练——解决“汉诺塔”问题 ...............................................................29
3.3.1 算法分析：情景模拟移动过程 .......................................................................29
3.3.2 具体实现 ...........................................................................................................30
3.4 算法演练——解决“阶乘”问题 ...................................................................32
3.4.1 算法分析：拆分调用 .......................................................................................32
3.4.2 具体实现：显示 6 以内阶乘过程 ...................................................................32
3.5 算法演练——进制转换器 ...............................................................................33
3.5.1 算法分析：除以 2 获取余数 ...........................................................................33
3.5.2 具体实现：输出十进制数字 10 对应的二进制数 .........................................33
3.6 算法演练——分解数字 ...................................................................................34
3.6.1 算法分析：递归除以 10 ..................................................................................34
3.6.2 具体实现：分解 5 位整数 12345 ....................................................................34
3.7 算法演练——解决二叉树遍历问题 ...............................................................34
3.7.1 算法分析：实现三种遍历方式 .......................................................................34
3.7.2 实现树的结构 ...................................................................................................35
3.7.3 二叉树递归遍历方案 .......................................................................................36
3.8 算法演练——公约数和小公倍数 .......................................................38
3.8.1 算法分析：整理计算流程 ...............................................................................38
3.8.2 基于递归算法的方案 .......................................................................................38
3.8.3 比较递归和非递归方案 ...................................................................................39
3.9 小结 ..................................................................................................................40
第 4 章 分治算法思想
4.1 分治算法思想基础 ..........................................................................................41
4.1.1 分治算法介绍与解题步骤 ...............................................................................41
4.1.2 分治算法的思路 ...............................................................................................41
4.1.3 分治算法能解决什么类型的问题 ...................................................................42
4.2 算法演练——二分法找出有序列表指定值 ...................................................43
4.2.1 算法分析：确定中位数 ...................................................................................43
4.2.2 种方案：先判断再查询 ...........................................................................43
4.2.3 第二种方案：判断某个元素是否在列表中 ...................................................44
4.2.4 第三种方案：找出有序列表中的指定值 .......................................................45
4.3 算法演练——求顺序表中数据的值 .......................................................45
4.3.1 算法分析：找出每一个分组中的值 .......................................................45
4.3.2 具体实现：找出给定列表 list 中的值 ....................................................46
4.4 算法演练——查找列表中元素的小值和值 .......................................46
4.4.1 算法分析：合理分组 .......................................................................................46
4.4.2 种方案：分组计算 ...................................................................................47
4.4.3 第二种方案：选择小元素 ...................................................................48
4.5 算法演练——找出一组序列中的第 k 小（大）的元素 ...............................48
4.5.1 算法分析：设置枢纽元素 ...............................................................................48
4.5.2 种方案：分组比较 ...................................................................................49
4.5.3 第二种方案：快速排序的分治算法 ...............................................................49
4.5.4 第三种方案：分组和排序同时进行 ...............................................................50
4.5.5 第四种方案：生成随机校验码 .......................................................................51
4.6 算法演练——快速排序 ...................................................................................51
4.6.1 算法分析：设定基准线并对比 .......................................................................51
4.6.2 具体实现 ...........................................................................................................52
4.6.3 第二种方案：列表推导 ...................................................................................52
4.7 算法演练——实现归并排序 ...........................................................................53
4.7.1 算法分析：中间下标与值大小分配 ...............................................................53
4.7.2 具体实现：对列表 [1,6,12,3,8] 进行归并排序 ..............................................54
4.8 算法演练——整数划分 ...................................................................................54
4.8.1 算法分析：梳理递归关系 ...............................................................................55
4.8.2 具体实现 ...........................................................................................................55
4.9小结 ..................................................................................................................56
第 5 章  贪心算法思想
5.1 贪心算法思想基础 ..........................................................................................57
5.1.1 贪心算法介绍 ...................................................................................................57
5.1.2 贪心算法的基本思路 .......................................................................................58
5.2 算法演练——解决“找零方案”问题 ...........................................................58
5.2.1 算法分析：零钱的面额是固定的 ...................................................................58
5.2.2 具体实现 ...........................................................................................................58
5.3 算法演练——解决“汽车加油”问题 ...........................................................59
5.3.1 算法分析：先加油后贪心 ...............................................................................59
5.3.2 具体实现 ...........................................................................................................59
5.4 算法演练——解决“求子元素之和问题”问题 ...................................60
5.4.1 算法分析：确定目前子元素的和是否 ...................................................60
5.4.2 具体实现：计算整数列表 s 的连续子元素之和 ...................................61
5.5 算法演练——解决“幼儿园分糖果”问题 ...................................................61
5.5.1 算法分析：优先从需求因子小的孩子进行尝试 ...........................................61
5.5.2 具体实现 ...........................................................................................................61
5.6 算法演练——圣诞节的礼物 ...........................................................................62
5.6.1 算法分析：单位价值 ...............................................................................62
5.6.2 具体实现 ...........................................................................................................63
5.7 算法演练——解决“活动安排”问题 ...........................................................64
5.7.1 算法分析：活动安排问题的解 ...............................................................64
5.7.2 个方案：快速排序 ...................................................................................65
5.7.3 第二个方案：通过冒泡排序同步交换数据 ...................................................66
5.8 算法演练——解决“摇摆序列”问题 ...........................................................67
5.8.1 算法分析：选择使得摇摆子序列长度更长的数 ...........................................67
5.8.2 具体实现 ...........................................................................................................68
5.9 算法演练——移除 k 个数字 ...........................................................................69
5.9.1 算法分析：从高位向低位遍历 .......................................................................69
5.9.2 具体实现 ...........................................................................................................70
5.10 算法演练——四种解决“霍夫曼编码”问题的方案 .................................70
5.10.1 算法分析 .........................................................................................................71
5.10.2 种方案：权值排序 .................................................................................72
5.10.3 第二种方案：使用 Python 自带的内置库 heapq .........................................73
5.10.4 第三种方案：使用内置统计函数 .................................................................75
5.10.5 第四种方案：实现完整树的队列操作 .........................................................76
5.11 算法演练——解决“Kruskal 算法”问题 ...................................................78
5.11.1 算法分析：顺序选取权重边 .........................................................................79
5.11.2 种方案：判断根结点是否相同 .............................................................80
5.11.3 第二种方案：将权重小的边加入到小生成树 .....................................81
5.11.4 第三种方案：基于不相交集实现 .................................................................83
5.12 算法演练——解决“Prim 算法”问题 ........................................................85
5.12.1 算法分析：将结点分组 .................................................................................86
5.12.2 种方案：选取权重小的一条边 .........................................................86
5.12.3 第二种方案：随机选取结点 .........................................................................87
5.13 小结 ................................................................................................................89