目录

第1章?Python算法入门 1

1.1　认识算法 1

1.1.1　什么是算法 1

1.1.2　算法的特性 2

1.2　程序、编程与算法之间的关系 3

1.2.1　算法与程序 3

1.2.2　算法与编程 4

1.3　算法的表示方法 5

1.3.1　用流程图表示算法 5

1.3.2　用N-S流程图表示算法 6

1.3.3　用计算机语言表示算法 8

1.4　基本数据类型 8

1.4.1　列表 9

1.4.2　元组 12

1.4.3　字典 13

1.4.4　集合 16

1.5　就业面试技巧与解析 18

1.5.1　面试技巧与解析（一） 18

1.5.2　面试技巧与解析（二） 19

第2章?Python算法与数据结构 20

2.1　链表 20

2.1.1　单链表 20

2.1.2　双链表 25

2.1.3　循环链表 30

2.1.4　链表的反转 35

2.1.5　链表的合并 37

2.2　栈 39

2.2.1　栈的基本操作 39

2.2.2　用链表实现栈 41

2.2.3　用数组实现栈 43

2.3　队列 45

2.3.1　队列的基本操作 45

2.3.2　用链表实现队列 46

2.3.3　用数组实现队列 49

2.4　用栈实现队列 51

2.5　用队列实现栈 53

2.6　就业面试技巧与解析 55

2.6.1　面试技巧与解析（一） 55

2.6.2　面试技巧与解析（二） 55

第3章?查找算法 57

3.1　顺序查找算法 57

3.1.1　顺序查找算法的原理 57

3.1.2　顺序查找算法的实现 59

3.1.3　顺序查找算法的性能分析 61

3.2　折半查找算法 62

3.2.1　折半查找算法的原理 62

3.2.2　折半查找算法的实现 63

3.2.3　折半查找算法的性能分析 64

3.3　插值查找算法 65

3.3.1　插值查找算法的原理 65

3.3.2　插值查找算法的实现 66

3.3.3　插值查找算法的性能分析 68

3.4　分块查找算法 68

3.4.1　分块查找算法的原理 68

3.4.2　分块查找算法的实现 70

3.4.3　分块查找算法的性能分析 71

3.5　哈希查找算法 71

3.5.1　哈希表和哈希函数 72

3.5.2　哈希函数的构造方法 72

3.5.3　碰撞与冲突问题 75

3.5.4　哈希查找算法的实现 77

3.6　查找算法时间复杂度的比较 78

3.7　就业面试技巧与解析 79

3.7.1　面试技巧与解析（一） 79

3.7.2　面试技巧与解析（二） 80

第4章?排序算法 81

4.1　排序算法的基础 81

4.1.1　排序的目的和过程 82

4.1.2　内部排序和外部排序 82

4.1.3　稳定排序和不稳定排序 83

4.2　选择排序算法 83

4.2.1　选择排序的思想 83

4.2.2　如何实现选择排序 85

4.3　冒泡排序算法 86

4.3.1　冒泡排序的思想 86

4.3.2　如何实现冒泡排序 87

4.4　插入排序算法 89

4.4.1　插入排序的思想 89

4.4.2　如何实现插入排序 91

4.5　归并排序算法 92

4.5.1　归并排序的思想 92

4.5.2　如何实现归并排序 93

4.6　希尔排序算法 95

4.6.1　希尔排序的思想 95

4.6.2　如何实现希尔排序 97

4.7　快速排序算法 98

4.7.1　快速排序的思想 98

4.7.2　如何实现快速排序 101

4.8　计数排序算法 102

4.8.1　计数排序的思想 102

4.8.2　如何实现计数排序 103

4.9　基数排序算法 104

4.9.1　基数排序的思想 104

4.9.2　如何实现基数排序 106

4.10　排序算法的比较 108

4.11　就业面试技巧与解析 108

4.11.1　面试技巧与解析（一） 108

4.11.2　面试技巧与解析（二） 109

第5章?树与二叉树算法 110

5.1　树 110

5.1.1　树的定义 110

5.1.2　树的基本概念 111

5.2　二叉树 112

5.2.1　二叉树的定义与性质 112

5.2.2　二叉树的存储 114

5.2.3　二叉树的遍历 115

5.3　特殊的二叉树结构 121

5.3.1　二叉搜索树（BST） 121

5.3.2　平衡二叉树（AVL树） 126

5.4　堆与二叉堆 132

5.4.1　最大堆与最小堆 132

5.4.2　二叉堆的存储 133

5.4.3　二叉堆的基本操作（上浮、下沉、插入、删除） 134

5.4.4　堆排序算法 137

5.5　就业面试技巧与解析 140

5.5.1　面试技巧与解析（一） 140

5.5.2　面试技巧与解析（二） 141

第6章?递归与分治算法 142

6.1　递归算法 142

6.1.1　什么是递归算法 142

6.1.2　递归算法的思想 143

6.2　递归算法的应用 144

6.2.1　计算n的阶乘 144

6.2.2　斐波那契数列问题 145

6.2.3　汉诺塔问题 147

6.2.4　递归求全排列 149

6.2.5　N皇后问题 151

6.3　分治算法 153

6.3.1　什么是分治算法 154

6.3.2　分治算法的思想 154

6.4　分治算法的应用 155

6.4.1　查找序列中的最大值与最小值 155

6.4.2　计算矩阵的乘积 158

6.4.3　解决多数元素问题 160

6.5　就业面试技巧与解析 161

6.5.1　面试技巧与解析（一） 161

6.5.2　面试技巧与解析（二） 162

第7章?贪心算法 163

7.1　什么是贪心算法 163

7.2　贪心算法的思想 164

7.3　贪心算法经典应用 165

7.3.1　汽车加油问题 165

7.3.2　货币选择问题 166

7.3.3　活动安排问题 167

7.3.4　最大子序和问题 168

7.3.5　背包问题 169

7.4　最小生成树问题 172

7.4.1　认识图 172

7.4.2　Kruskal算法 174

7.4.3　Prim算法 177

7.5　哈夫曼树问题 179

7.6　就业面试技巧与解析 183

7.6.1　面试技巧与解析（一） 183

7.6.2　面试技巧与解析（二） 184

第8章?动态规划算法 185

8.1　动态规划的基本思想 185

8.2　线性动态规划 187

8.2.1　最长递增子序列 187

8.2.2　最长公共子序列 189

8.2.3　编辑距离问题 191

8.3　区域动态规划 192

8.3.1　石子合并问题 193

8.3.2　矩阵链乘法 195

8.4　树形动态规划 197

8.4.1　最大路径和问题 197

8.4.2　树中距离之和问题 198

8.4.3　最大独立集问题 201

8.5　背包动态规划 203

8.5.1　0-1背包问题 203

8.5.2　完全背包问题 204

8.6　就业面试技巧与解析 206

8.6.1　面试技巧与解析（一） 206

8.6.2　面试技巧与解析（二） 207

第9章?使用Python算法解决经典问题 209

9.1　最大公约数 209

9.1.1　问题描述 210

9.1.2　算法分析 210

9.1.3　算法实现 210

9.2　寻找水仙花数 211

9.2.1　问题描述 211

9.2.2　算法分析 211

9.2.3　算法实现 211

9.3　鸡兔同笼问题 212

9.3.1　问题描述 212

9.3.2　算法分析 212

9.3.3　算法实现 213

9.4　猴子分桃问题 214

9.4.1　问题描述 214

9.4.2　算法分析 214

9.4.3　算法实现 214

9.5　爱因斯坦阶梯问题 215

9.5.1　问题描述 215

9.5.2　算法分析 215

9.5.3　算法实现 215

9.6　多进程验证哥德巴赫猜想 217

9.6.1　问题描述 217

9.6.2　算法分析 217

9.6.3　算法实现 218

9.7　黄金矿工问题 220

9.7.1　问题描述 220

9.7.2　算法分析 220

9.7.3　算法实现 221

9.8　凯撒密码问题 222

9.8.1　问题描述 222

9.8.2　算法分析 222

9.8.3　算法实现 223

9.9　约瑟夫环问题 224

9.9.1　问题描述 224

9.9.2　算法分析 224

9.9.3　算法实现 225

9.10　股票交易问题 228

9.10.1　问题描述 228

9.10.2　算法分析 228

9.10.3　算法实现 231

9.10.4　问题的变形 231