本书主要内容包括: 算法基础 、 排序算法 、 查找算法 、 双指针 、 哈希算法 、 深度优先搜索 、 广度优先搜索 、 回溯算法 、 动态规划 、 贪心算法 、 分治算法 、 并查集 、 *短路径 、 数论算法 等。

第1章 算法初步 1 1.1 什么是算法 1 1.1.1 算法的定义 1 1.1.2 算法与程序的区别 1 1.2 时间复杂度 2 1.2.1 运行时间和程序复杂程度的 关系 2 1.2.2 时间复杂度是渐进的 2 1.2.3 简单程序的时间复杂度分析 3 1.2.4 时间复杂度的意义 6 1.3 空间复杂度 8 1.4 算法的应用 8 1.5 Python算法的优势 9 1.6 小结 9 1.7 习题 10 第2章 排序算法 12 2.1 初级排序算法 12 2.1.1 插入排序 12 2.1.2 选择排序 14 2.1.3 冒泡排序 17 2.2 **排序算法 19 2.2.1 归并排序 19 2.2.2 快速排序 21 2.2.3 希尔排序 24 2.2.4 堆排序 26 2.2.5 桶排序 30 2.3 小结 32 2.4 习题 32 第3章 查找 34 3.1 顺序查找 34 3.2 二分查找 35 3.3 树 41 3.4 二叉树 43 3.4.1 二叉树的性质 43 3.4.2 满二叉树 44 3.4.3 完全二叉树 44 3.4.4 创建二叉树 45 3.4.5 遍历二叉树 46 3.5 二叉搜索树 47 3.5.1 二叉搜索树基础 47 3.5.2 二叉搜索树的操作 47 3.6 平衡二叉树 56 3.6.1 二叉搜索树的效率 56 3.6.2 AVL树 56 3.7 小结 62 3.8 习题 62 第4章 双指针问题 65 4.1 单链表 65 4.1.1 建立单链表 65 4.1.2 遍历单链表 66 4.1.3 插入单链表 66 4.1.4 删除单链表第n个数 68 4.2 双指针的应用 69 4.2.1 数组合并问题 69 4.2.2 删除单链表倒数第n个数 71 4.3 小结 72 4.4 习题 72 第5章 哈希算法 73 5.1 哈希算法的原理 73 5.2 哈希函数 74 5.2.1 除法哈希算法 74 5.2.2 乘法哈希算法 75 5.2.3 平方取中法 75 5.2.4 随机数哈希算法 75 5.3 解决冲突 76 5.3.1 开放定址法 76 5.3.2 拉链址法 77 5.4 哈希算法的应用 78 5.4.1 两个数的和问题 78 5.4.2 团体赛问题 79 5.4.3 猜数字游戏 81 5.5 小结 83 5.6 习题 83 第6章 深度优先搜索算法 85 6.1 搜索 85 6.2 图上的深度优先搜索 85 6.2.1 无向图 85 6.2.2 图的术语 86 6.2.3 图上的搜索 88 6.2.4 经典例题讲解(*大的油田) 89 6.3 二叉树上的深度优先搜索 91 6.3.1 二叉树相关术语 91 6.3.2 二叉树上的搜索 92 6.3.3 经典例题讲解(员工派对) 92 6.3.4 经典例题讲解(城市危机) 97 6.4 小结 105 6.5 习题 106 第7章 广度优先搜索算法 107 7.1 依旧是图的搜索 107 7.2 队列中的存储方式 108 7.3 经典例题讲解 111 7.3.1 艰难旅行 111 7.3.2 混乱地铁 114 7.3.3 温室大棚 116 7.4 小结 120 7.5 习题 120 第8章 回溯算法 121 8.1 回溯算法原理 121 8.2 回溯算法的应用 124 8.2.1 N皇后 124 8.2.2 数独 128 8.2.3 排列组合 132 8.2.4 两个扩展问题 137 8.3 小结 139 8.4 习题 139 第9章 动态规划 141 9.1 动态规划介绍 141 9.2 矿工问题 141 9.2.1 问题描述 141 9.2.2 问题分析 142 9.2.3 参考实现 145 9.3 爬楼梯问题 146 9.3.1 问题描述 146 9.3.2 问题分析 147 9.3.3 参考实现 149 9.4 背包问题 149 9.4.1 问题描述 149 9.4.2 问题分析 150 9.4.3 问题实例 151 9.4.4 参考实现 153 9.5 *长递增子序列问题 154 9.5.1 问题描述 154 9.5.2 改进算法 155 9.5.3 参考实现 156 9.6 小结 157 9.7 习题 157 第10章 贪心算法 158 10.1 贪心算法介绍 158 10.2 硬币找零问题 159 10.2.1 问题描述 159 10.2.2 问题实例 159 10.2.3 参考实现 160 10.3 活动安排问题 160 10.3.1 问题描述 160 10.3.2 参考实现 161 10.4 哈夫曼编码 162 10.4.1 问题描述 163 10.4.2 哈夫曼树 163 10.4.3 贪心选择性质 165 10.4.4 *优子结构性质 166 10.4.5 参考实现 166 10.5 小结 167 10.6 习题 168 第11章 分治算法 169 11.1 分治算法原理 169 11.2 分治算法应用 170 11.2.1 二分查找 170 11.2.2 二维数组的查找 171 11.2.3 快速凸包算法 173 11.2.4 快速傅氏变换 178 11.3 小结 183 11.4 习题 183 第12章 并查集 184 12.1 并查集介绍 184 12.1.1 并查集的构造方法 184 12.1.2 并查集的应用 184 12.1.3 并查集3种基本操作的Python实现 186 12.2 朋友圈 187 12.2.1 问题描述 187 12.2.2 问题分析 187 12.2.3 代码 188 12.3 图的子元素 190 12.3.1 问题描述 190 12.3.2 问题分析 190 12.3.3 代码 192 12.4 小结 193 12.5 习题 193 第13章 *短路径算法 194 13.1 戴克斯特拉算法 194 13.1.1 算法介绍 194 13.1.2 算法证明 199 13.1.3 算法代码 200 13.2 贝尔曼-福特算法 202 13.2.1 算法介绍 203 13.2.2 算法证明 205 13.2.3 算法代码 206 13.3 弗洛伊德算法 208 13.3.1 算法介绍 208 13.3.2 算法代码 212 13.4 A*搜索算法 215 13.4.1 算法介绍 215 13.4.2 算法证明 219 13.4.3 算法代码 220 13.5 习题 222 第14章 数论算法 223 14.1 欧几里得算法 223 14.1.1 算法分析与证明 223 14.1.2 算法代码 224 14.1.3 算法应用 224 14.2 中国余数定理 228 14.2.1 算法介绍 228 14.2.2 算法证明 229 14.2.3 算法代码 229 14.3 素性检验算法 230 14.3.1 费马素性检验 230 14.3.2 米勒-拉宾素性检验 231 14.3.3 算法代码 233 14.4 小结 234 14.5 习题 234

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