你也能看得懂的Python算法书

很资深：凝聚4位作者10年编程经验，带你领悟算法的精髓

很有趣：全书采用生动风趣的语言，让算法不再难学

很实战：全书包括36个实例，9大类算法，很有实战价值

很图解：对每种算法，都给出了图解说明，保证一学就会

 

编程的核心是算法，学习算法不仅能教会你解决问题的方法，而且还能为你今后的发展提供一种可能。本书面向算法初学者，首先介绍当下流行的编程语言Python，详细讲解了Python语言的变量和顺序、分支、循环三大结构，以及列表和函数的使用，为之后学习算法打好基础。然后以通俗生动的语言讲解了双指针、哈希、深度优先、广度优先、回溯、贪心、动态规划和*短路径等经典算法。

王硕，资深软件工程师、北京理工大学客座讲师，从事计算机教育多年，擅长Python、Java、C语言、数据结构和算法等，接触数千学生，对算法有独到见解。平行致力于企业级软件开发和计算机教育工作，具有索尼中国研究院、四大国有银行软件开发中心工作经历。

董文馨，已获得美国斯坦福大学计算机专业Offer的IB高中生，学校编程俱乐部创办人。从10岁开始在国外上学，精通英语，西班牙语，对数学，物理，和电脑科学有天赋。曾创办个人文化交流网站，未来打算从事人工智能领域的工作。

张舒行，五年多机器人比赛经验，长时间负责队内编程, 曾参加FLL, VEX, 现为FRC队伍5823队员。擅长数学，曾在各大竞赛中获奖。

张洁，中科院软件所博士，计算机科班出身，多年国有大型银行信息系统开发及管理经验。发表SCI、EI检索论文十余篇，在计算机图形学、信息系统架构方面有较深造诣。

第1章　编程基础 1
1.1 变量 1
1.1.1 输出和输入 2
1.1.2 简单变量类型 3
1.1.3 数学计算 6
1.1.4 位运算 7
1.1.5 使用字符串 11
1.2 三大结构 15
1.2.1 循序结构 15
1.2.2　分支结构 16
1.2.3 条件判断 18
1.2.4 应用分支结构 20
1.2.5 循环结构 21
1.2.6 continue和break 23
1.2.7 应用循环结构 24
1.2.8 结构的嵌套 26
1.3 列表 27
1.3.1 定义列表 27
1.3.2 对元素进行操作 28
1.3.3 列表的顺序 31
1.3.4 列表内置函数 33
1.3.5 截取和拼接列表 36
1.3.6 字符串、元组和列表 38
1.3.7 用循环遍历列表 40
1.3.8 字典简介 41
1.4 函数 43
1.4.1 定义子函数 43
1.4.2 主函数 44
1.4.3 调用函数 45
1.4.4 全局变量 47
1.4.5 函数的运用 48

第2章　双指针问题 53
2.1 数组合并 53
2.1.1 合并有序数组 53
2.1.2 终代码 56
2.2 二分查找 56
2.2.1 什么是二分查找 57
2.2.2 问题求解 58
2.2.3 终代码 60
2.3 链表 60
2.3.1 什么是单链表 60
2.3.2 建立单链表 61
2.3.3 建立双链表 63
2.3.4 双向输出双链表 65
2.3.5 向单链表中添加元素 66
2.3.6 向双链表中添加元素 69
2.3.7 删除列表中的元素 71

第3章　哈希算法 75
3.1 什么是哈希 75
3.2　两个数的和 78
3.2.1 问题求解1 78
3.2.2 解法1的终代码 80
3.2.3 问题求解2 81
3.2.4 解法2的终代码 82
3.3 单词模式匹配 82
3.3.1 问题求解 83
3.3.2 终代码 85
3.4 猜词游戏 85
3.4.1 问题求解 87
3.4.2 终代码 88
3.5 神奇的词根 89
3.5.1 问题求解 90
3.5.2 终代码 92

第4章　深度优先遍历 93
4.1 什么是深度优先遍历 93
4.2 二叉树 95
4.2.1 二叉树的类型 95
4.2.2 二叉树的相关术语 96
4.2.3 二叉树的节点代码 97
4.2.4 二叉树的遍历顺序 97
4.2.5 深度优先遍历与广度优先遍历 97
4.3 怎么抓住小偷 98
4.3.1 解题思路 98
4.3.2 从思路到代码 102
4.4 二叉树中的路径和 102
4.4.1 解题思路 103
4.4.2 完整代码 112
4.5 的岛屿 113
4.5.1 解题思路 113
4.5.2 完整代码 116

第5章　广度优先遍历 118
5.1 什么是广度优先遍历 118
5.2 选课的智慧 120
5.2.1 广度优先遍历 121
5.2.2 问题求解 122
5.2.3 终代码 124
5.3 寻找制高点 125
5.3.1 问题求解 126
5.3.2 集合 129
5.3.3 终代码 130
5.4 合法的括号 131
5.4.1 问题求解 131
5.4.2 终代码 135
5.5 树的右侧 136
5.5.1 问题求解 136
5.5.2 终代码 139

第6章　回溯算法 141
6.1 什么是回溯 141
6.2 遍历所有排序方式 142
6.2.1 问题求解 142
6.2.2 终代码 144
6.3 经典问题的组合 147
6.3.1 问题求解 147
6.3.2 终代码 149
6.4 查找单词问题 151
6.4.1 问题求解 152
6.4.2 终代码 155
6.5 八皇后问题 157
6.5.1 问题求解 158
6.5.2 终代码 160
6.6 教你解数独 164
6.6.1 问题求解 165
6.6.2 终代码 168

第7章　贪心算法 172
7.1 硬币找零问题 173
7.1.1　问题描述 173
7.1.2　终代码 175
7.2　活动安排问题 175
7.2.1 问题描述 176
7.2.2 终代码 177
7.3　哈夫曼编码 178
7.3.1　问题描述 178
7.3.2　哈夫曼树 179
7.3.3　贪心选择性质 181
7.3.4　子结构性质 182
7.3.5　终代码 183

第8章　动态规划算法 185
8.1 爬楼梯问题 185
8.1.1 问题描述 186
8.1.2　终代码 188
8.2 矿工挖矿问题 189
8.2.1 问题描述 189
8.2.2　终代码 195
8.3　背包问题 195
8.3.1　问题描述 195
8.3.2　问题实例 196
8.3.3　终代码 201
8.4　长递归子序列问题 202
8.4.1　问题描述 202
8.4.2　改进算法 204
8.4.3　终代码 205

第9章　短路径问题 207
9.1 迪可斯特朗算法 207
9.1.1 术语释义 208
9.1.2 问题示例：短公交线路 208
9.1.3 图与节点的定义 209
9.1.4 把图用代码“画”出来 210
9.1.5 算法核心：两个节点集合 210
9.1.6 算法核心：循环 210
9.1.7 输出路线 211
9.1.8 通过示例理解算法 211
9.1.9 完整代码展示 214
9.2 Floyd算法 216
9.2.1 算法核心：两个矩阵 216
9.2.2 算法核心：通过中介点缩短距离 217
9.2.3 通过示例理解算法 218
9.2.4 完整代码 222
9.3 A*算法 223
9.3.1 算法核心：迪可斯特朗算法 223
9.3.2 算法核心：预估函数 224
9.3.3 算法核心：选择预估函数 226
9.3.4 A*算法的兄弟们 226

第10章　分治算法 227
10.1 什么是分治 227
10.2 归并排序 228
10.2.1 递归法与迭代法 228
10.2.2 递归法描述 229
10.2.3 迭代法描述 232
10.2.4 终代码 233
10.3 连续子列表的和 235
10.3.1 解题思路 235
10.3.2 终代码 237
10.4 几何问题之凸包 238
10.4.1 问题求解 238
10.4.2 终代码 240
10.5 数学问题之多项式乘法 242
10.5.1 问题求解 242
10.5.2 终代码 245

言

为什么要写这本书 

算法是编程的核心，就像一台计算机的CPU，算法的好坏决定了一个系统的效率高低。 

许多人认为学习编程就是学习的编程语言、技术和框架，其实计算机算法更重要。计算机语言和技术日新月异，但万变不离其宗的是算法。修炼好算法这门“内功”，再辅以新技术这些“招式”，才能独霸“武林”。这也是为什么像Google和Facebook这类大公司在面试中主要会考查算法问题的原因。 

目前图书市场上关于算法的图书不少，经典的如《算法导论》。但是大多数算法图书太学术、太复杂，对于初学者来说门槛太高。学习算法本身就不是一件容易的事情，再加上复杂的场景和数学理论，会让算法的学习曲线更陡。因此本书的作者们就萌生了写一本让大家都能看懂的算法书的想法，以生动的语言把算法的思想过程写出来，让学习算法不再那么枯燥。 

在本书的创作过程中，王硕老师迎来了人生的个宝宝小朗朗。于是几位作者就有了一个心愿，希望青少年朋友也学会算法，因此，在描述算法问题时，尽量用简单、通俗的形式表述，使青少年朋友也能看懂，也希望如此这般能够增加读者的学习兴趣。既然是学习算法，免不了要写代码，对于编程语言的选择，我们选择了Python这门简单易懂的语言作为本书的编程语言。对于初学编程的人来说，Python可以缩短学习编程语言的时间和降低学习编程的难度。 

学习算法不易，且行且珍惜。

本书有何特色 

1. 以孩子的口吻，生动形象地讲解算法，提高趣味性 

为了便于读者理解本书内容，提高学习效率，大部分问题都以孩子的口吻来讲解，以解决小朗朗的实际问题作为出发点引出问题，增加了趣味性和可读性。 

2. 涵盖核心算法知识点 

本书涵盖双指针问题、哈希、深度优先遍历、广度优先遍历、回溯、贪心、动态规划、短路径问题、分治等9大算法，帮助读者全面掌握核心算法的知识点。 

3. 以Python语言作为载体，降低学习难度 

抛弃其他复杂的编程语言，本书采用简单的编程语言Python作为算法的载体，并在第1章介绍了Python语言的语法。 

4. 选择经典算法的经典问题，有较高的通用性 

本书在简单介绍Python编程语言以后，选择了9大经典算法，重点讲解算法原理，并选择经典问题进行有针对性的练习。 

5. 提供完善的技术支持和售后服务 

本书提供了专门的邮箱供读者咨询：[email protected]。读者在阅读本书的过程中有任何疑问都可以通过该邮箱获得帮助。 

本书内容及知识体系 

第1章 编程基础 

掌握一门编程语言是学习算法的基础。学习编程语言是为了与计算机“交流”，只有正确的格式才能被计算机成功识别。学习编程语言的起点就是了解这门语言的语法。本书使用Python语言进行算法讲解，本章主要讲解Python 3的编程语法。 

第2章 双指针问题 

“指针”是编程语言中的一个对象，它存储着一个内存空间的地址，计算机可以通过这个地址找到变量的值。也就是说，这个特定的地址指向这个特定的值。指针的优点在于它可以有效利用零碎的内存空间。

第3章 哈希算法 

哈希算法又称散列函数算法，是一种查找算法，简单来说，就是把一些复杂的数据，通过某种函数映射关系，映射成更加易于查找的方式。但是这种映射关系有可能会发生多个关键字映射到同一地址的现象，我们称之为冲突。在这种特殊情况下，需要对关键字进行第二次或更多次的处理，在其他的大多数情况下，哈希算法可以实现在常数时间内存储和查找这些关键字。 

第4章 深度优先遍历算法 

深度优先遍历算法是经典的图论算法，它的搜索逻辑就和它的名字一样，只要有可能，就尽量深入搜索，直到找到答案，或者尝试了所有可能后确定没有解。 

第5章 广度优先遍历算法 

广度优先遍历算法与深度优先遍历算法类似，也是查询的方法之一，它从某个状态出发查询可以到达的所有状态。但不同于深度优先遍历，广度优先遍历算法总是先去查询距离初始状态近的状态。 

第6章 回溯算法 

回溯算法可以被看作走迷宫，因为我们不知道出口在哪里，所以只能不断地深入，尝试不同的路线。一旦找到了出口便可以回溯到起点，辨清路线。 

第7章 贪心算法 

贪心算法就是遵循某种既定原则，不断地选取当前条件下的选择来构造每个子步骤的解决方案，直到获得问题终的解。即在对问题求解时，总是做出在当前看来是好的选择。也就是说，不从整体上加以考虑，它所做的仅是在某种意义上的局部解。 

第8章 动态规划算法 

动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，终获得原始问题的解，避免了对交叠子问题的重复求解。 

第9章 短路径问题 

把地点看成节点，把道路看成边，整个地图就可看成一个加权图。计算加权图中两点间的短路径是编程的一个重要问题，这一章我们会用以下几个算法解决这个问题：迪可斯特朗算法、Floyd算法、A*算法。

第10章 分治算法 

分治算法的核心思想是把一个规模很大的问题化简为多个规模较小的问题，这些子问题虽然独立而不同，但是问题的本质是一致的，从而达到分而治之的目的。 

适合阅读本书的读者 

• 需要全面学习算法的人员 

• 需要学习Python的程序员 

• 对编程算法感兴趣的人员 

• 希望提高算法水平的程序员 

• 专业培训机构的学员 

阅读本书的建议 

• 没有Python基础的读者，建议从第1章开始顺次阅读并演练每个实例。 

• 有一定Python基础的读者，可以根据实际情况有重点地选择阅读各个模块和项目案例。 

• 对于每个模块和案例，先自己思考一下实现的思路，然后再阅读，学习效果会更好。这样理解起来也会更加容易、更加深刻。