编程的核心是算法，学习算法不仅能教会你解决问题的方法，而且还能为你今后的发展提供一种可能。本书面向算法初学者，首先介绍当下流行的编程语言Python，详细讲解了Python语言的变量和顺序、分支、循环三大结构，以及列表和函数的使用，为之后学习算法打好基础。然后以通俗生动的语言讲解了双指针、哈希、深度优先、广度优先、回溯、贪心、动态规划和*短路径等经典算法。
第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
算法定义
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
一个算法应该具有以下七个重要的特征：
①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
②确切性(Definiteness)：算法的每一步骤必须有确切的定义；
③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输 入是指算法本身定出了初始条件；
④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的；
⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
⑥高效性(High efficiency)：执行速度快，占用资源少；
⑦健壮性(Robustness)：对数据响应正确。
2. 时间复杂度
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。）表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
大O，简而言之可以认为它的含义是“order of”（大约是）。
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n^2 - 2n + 2。
当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略——举例说明：当 n = 500，4n^2; 项是 2n 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
# Filename : test.py # author by : www.runoob.com # 定义一个函数 def hcf(x, y): """该函数返回两个数的最大公约数""" # 获取最小值 if x > y: smaller = y else: smaller = x for i in range(1,smaller + 1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf # 用户输入两个数字 num1 = int(input("输入第一个数字: ")) num2 = int(input("输入第二个数字: ")) print( num1,"和", num2,"的最大公约数为", hcf(num1, num2))执行以上代码输出结果为：
输入第一个数字: 54
输入第二个数字: 24
54 和 24 的最大公约数为 6