Python常用算法手册

图书标准信息

• 作者 徐庆丰
• 出版社 中国铁道出版社
• 出版时间 2020-08
• 版次 1
• ISBN 9787113267445
• 定价 59.80元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 308页
• 字数 468千字

【内容简介】

算法是程序的灵魂，算法能够告诉开发者在面对一个项目功能时用什么思路去实现，有了这个思路后，编程工作只需遵循这个思路去实现即可。本书循序渐进、由浅入深地详细讲解了算法实现的核心技术，全书共12章，分别讲解了初步认识算法思想，枚举算法思想，递归算法思想，分治算法思想，贪心算法思想，回溯算法思想，迭代算法思想，查找算法，排序算法，使用算法解决数据结构问题，解决数学问题，经典算法问题。全书通过具体实例的实现过程演练了各个知识点的具体使用流程，引领读者全面掌握算法的核心技术。

【作者简介】

     徐庆丰，西安交通大学计算机硕士，软件工程硕士。就职于360移动端项目组，专门解决移动Android设备方面的数据加密、漏洞校验分析和加密工作。精通C、C  、Python、Java，擅长数据分析、机器学习、网络攻击、漏洞查找分析、系统安全架构和反编译。2010年，曾经率先发现微软IE7的重大漏洞，并提出了具体的补丁方案，引起微软重视，并建议加入微软MVP。

【目录】

第 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