正版 代码随想录——跟着Carl学算法 孙秀洋 电子工业出版社 9787

目录 章 准备面试要知己知彼 1 1.1 面试官为什么要考查算法 1 1.2 编程语言 2 1.2.1 学好算法之前更要学好编程语言 2 1.2.2 代码规范 2 1.3 如何写简历 5 1.3.1 简历模板 5 1.3.2 谨慎使用“精通” 5 1.3.3 拿不准的内容绝对不要写在简历上 5 1.3.4 项目经验应该如何写 6 1.3.5 博客的重要性 7 1.4 企业技术面试的流程 7 1.4.1 一面——机试面 7 1.4.2 二面——基础算法面 8 1.4.3 三面——综合技术面 8 1.4.4 四面——技术leader面 8 1.4.5 五面——HR面 9 1.5 本章小结 10 第2章 程序的性能分析 11 2.1 时间复杂度分析 11 2.1.1 什么是时间复杂度 11 2.1.2 如何描述时间复杂度 12 2.1.3 递归算法的时间复杂度分析 14 2.2 程序的运行时间 17 2.2.1 超时是怎么回事 17 2.2.2 从硬件配置看计算机的性能 18 2.2.3 测试计算机的运行速度 18 2.3 编程语言的内存管理 20 2.3.1 C++的内存管理 21 2.3.2 如何计算程序占用多少内存 22 2.3.3 内存对齐 22 2.4 空间复杂度分析 24 2.4.1 什么是空间复杂度 24 2.4.2 递归算法的空间复杂度分析 25 2.4.3 以空间换时间是常见的优化思路 32 2.5 本章小结 33 第3章 数组 34 3.1 数组理论基础 34 3.2 二分查找 36 3.2.1 二分法写法（一） 37 3.2.2 二分法写法（二） 38 3.3 移除元素 39 3.3.1 暴力解法 40 3.3.2 双指针法 41 3.4 长度最小的子数组 42 3.4.1 暴力解法 42 3.4.2 滑动窗口 43 3.5 这个循环转懵了很多人 45 3.5.1 循环不变量 45 3.5.2 代码实现 46 3.6 本章小结 48 第4章 链表 49 4.1 链表理论基础 49 4.1.1 链表的类型 49 4.1.2 链表的存储方式 50 4.1.3 链表的定义 51 4.1.4 链表的操作 52 4.1.5 性能分析 52 4.2 用虚拟头节点会方便得多 53 4.3 链表常见的六个操作 57 4.4 反转链表 60 4.4.1 双指针法 60 4.4.2 递归法 61 4.5 删除倒数第n个节点 62 4.6 环形链表 64 4.6.1 判断链表是否有环 65 4.6.2 寻找环的入口 66 4.7 本章小结 69 第5章 哈希表 70 5.1 哈希表理论基础 70 5.1.1 哈希函数 71 5.1.2 哈希碰撞 71 5.1.3 常见的三种哈希结构 73 5.2 有效的字母异位词 74 5.3 两个数组的交集 76 5.4 两数之和 78 5.5 四数相加 80 5.6 三数之和 81 5.6.1 哈希解法 81 5.6.2 双指针法 82 5.7 四数之和 85 5.8 本章小结 87 第6章 字符串 88 6.1 字符串与数组的区别 88 6.2 反转字符串 89 6.3 反转字符串II 90 6.4 反转字符串里的单词 92 6.5 KMP算法理论基础 96 6.5.1 什么是KMP算法 96 6.5.2 什么是前缀表 96 6.5.3 为什么一定要用前缀表 97 6.5.4 如何计算前缀表 98 6.5.5 时间复杂度分析 100 6.6 使用KMP匹配字符串 101 6.6.1 构造next数组 101 6.6.2 使用next数组做匹配 103 6.6.3 前缀表统一减一的代码实现 104 6.6.4 前缀表（不减一）的代码实现 105 6.7 找到重复的子字符串 107 6.8 本章小结 109 第7章 栈与队列 110 7.1 栈与队列理论基础 110 7.2 用栈组成队列 112 7.3 用队列组成栈 114 7.3.1 使用两个队列实现栈 115 7.3.2 使用一个队列实现栈 117 7.4 匹配括号 118 7.5 逆波兰表达式 120 7.6 滑动窗口优选值 122 7.7 前k个高频元素 126 7.8 接雨水 129 7.8.1 双指针解法 130 7.8.2 动态规划解法 132 7.8.3 单调栈解法 133 7.9 本章小结 137 第8章 二叉树 139 8.1 二叉树理论基础 139 8.1.1 二叉树的种类 139 8.1.2 二叉树的存储方式 141 8.1.3 二叉树的遍历方式 142 8.1.4 二叉树的定义 143 8.2 前中后序的递归遍历 144 8.3 前中后序的迭代遍历 146 8.3.1 前序遍历 146 8.3.2 中序遍历 147 8.3.3 后序遍历 148 8.4 前、中、后序统一迭代法 149 8.5 二叉树的层序遍历 152 8.6 反转二叉树 155 8.6.1 递归法 156 8.6.2 迭代法 156 8.7 对称二叉树 158 8.7.1 递归法 159 8.7.2 迭代法 162 8.8 二叉树的优选深度 164 8.8.1 递归法 165 8.8.2 迭代法 166 8.9 二叉树的最小深度 167 8.9.1 递归法 168 8.9.2 迭代法 170 8.10 平衡二叉树 170 8.10.1 递归法 173 8.10.2 迭代法 175 8.11 二叉树的所有路径 176 8.11.1 递归法 177 8.11.2 迭代法 182 8.12 路径总和 183 8.12.1 递归法 183 8.12.2 迭代法 186 8.12.3 路径总和II 187 8.13 构造一棵二叉树 189 8.13.1 使用中序与后序遍历序列构造二叉树 189 8.13.2 使用前序与中序遍历序列构造二叉树 195 8.13.3 相关思考 197 8.14 合并两棵二叉树 197 8.14.1 递归 198 8.14.2 迭代法 200 8.15 在二叉搜索树中寻找节点 201 8.15.1 递归法 202 8.15.2 迭代法 203 8.16 验证二叉搜索树 204 8.16.1 递归法 205 8.16.2 迭代法 207 8.17 二叉搜索树的最小绝对差 208 8.17.1 递归法 208 8.17.2 迭代法 209 8.18 二叉搜索树中的众数 210 8.18.1 递归法 211 8.18.2 迭代法 215 8.19 二叉树的最近公共祖先 216 8.19.1 普通二叉树 216 8.19.2 二叉搜索树 221 8.20 在二叉搜索树中插入一个节点 224 8.20.1 递归法 225 8.20.2 迭代法 227 8.21 在二叉搜索树中删除一个节点 228 8.21.1 递归法 228 8.21.2 迭代法 230 8.22 修剪二叉搜索树 231 8.22.1 递归法 232 8.22.2 迭代法 234 8.23 构造一棵平衡二叉搜索树 235 8.23.1 递归法 236 8.23.2 迭代法 238 8.24 本章小结 239 第9章 回溯算法 240 9.1 回溯算法理论基础 240 9.1.1 什么是回溯算法 240 9.1.2 回溯法的性能 240 9.1.3 回溯法可以解决的问题 240 9.1.4 如何理解回溯法 241 9.1.5 回溯法模板 241 9.2 组合问题 243 9.2.1 回溯算法 244 9.2.2 剪枝优化 248 9.3 组合总和（一） 250 9.3.1 回溯算法 251 9.3.2 剪枝优化 254 9.4 电话号码的字母组合 255 9.5 组合总和（二） 260 9.5.1 回溯算法 261 9.5.2 剪枝优化 263 9.6 组合总和（三） 265 9.7 分割回文串 270 9.8 复原IP地址 274 9.9 子集问题（一） 279 9.10 子集问题（二） 281 9.11 递增子序列 284 9.11.1 回溯算法 285 9.11.2 哈希优化 287 9.12 排列问题（一） 288 9.13 排列问题（二） 291 9.13.1 回溯算法 291 9.13.2 拓展 293 9.14 N皇后问题 296 9.15 解数独 301 9.15.1 回溯算法 302 9.15.2 判断棋盘是否合法 304 9.16 本章小结 305 0章 贪心算法 306 10.1 贪心算法理论基础 306 10.1.1 什么是贪心 306 10.1.2 贪心的套路 306 10.2 分发饼干 307 10.3 摆动序列 309 10.4 优选子序和 312 10.5 买卖股票的最佳时机II 314 10.6 跳跃游戏 316 10.7 跳跃游戏II 318 10.7.1 贪心解法（一） 320 10.7.2 贪心解法（二） 320 10.8 加油站 322 10.8.1 暴力解法 323 10.8.2 贪心解法（一） 324 10.8.3 贪心解法（二） 325 10.9 分发糖果 327 10.10 柠檬水找零 330 10.11 用最少数量的箭射爆气球 332 10.12 合并区间 335 10.13 单调递增的数字 338 10.13.1 暴力解法 338 10.13.2 贪心解法 339 10.14 本章小结 340 1章 动态规划 341 11.1 动态规划理论基础 341 11.1.1 动态规划题目的解题步骤 341 11.1.2 动态规划应该如何排查问题 342 11.2 斐波那契数 343 11.2.1 动态规划解法 344 11.2.2 递归解法 345 11.3 爬楼梯 346 11.4 使用最低花费爬楼梯 349 11.5 不同路径（一） 353 11.5.1 深度优先搜索 354 11.5.2 动态规划 355 11.5.3 数论方法 356 11.6 不同路径（二） 358 11.7 整数拆分 361 11.7.1 动态规划 362 11.7.2 贪心算法 364 11.8 不同的二叉搜索树 364 11.9 0-1背包理论基础 369 11.9.1 二维dp数组 370 11.9.2 一维dp数组 375 11.10 分割等和子集 379 11.11 目标和 382 11.12 一和零 385 11.13 完全背包理论基础 388 11.14 零钱兑换（一） 392 11.15 拼凑一个正整数 395 11.16 多步爬楼梯 398 11.17 零钱兑换（二） 399 11.18 完全平方数 402 11.19 单词拆分 405 11.19.1 回溯算法 406 11.19.2 背包问题 407 11.20 买卖股票的最佳时机 410 11.20.1 暴力枚举 410 11.20.2 贪心算法 411 11.20.3 动态规划 411 11.21 买卖股票的最佳时机II 414 11.22 买卖股票的最佳时机III 416 11.23 买卖股票的最佳时机IV 420 11.24 最佳买卖股票时机（含冷冻期） 423 11.25 买卖股票的最佳时机（含手续费） 426 11.26 最长递增子序列 428 11.27 最长连续递增序列 430 11.27.1 动态规划 430 11.27.2 贪心算法 432 11.28 最长重复子数组 433 11.29 最长公共子序列 436 11.30 不相交的线 438 11.31 优选子序和 440 11.32 判断子序列 441 11.33 不同的子序列 444 11.34 两个字符串的删除操作 447 11.35 编辑距离 450 11.36 回文子串 453 11.36.1 动态规划 453 11.36.2 双指针法 456 11.37 最长回文子序列 457 11.38 本章小结

孙秀洋，哈尔滨工业大学计算机科学与技术专业硕士毕业，在校期间获得ACM/ICPC（靠前大学生程序设计竞赛）亚洲区域赛铜牌。先后在腾讯和百度从事技术研发工作多年，对数据结构和算法有深刻理解。CSDN博客专家，各大OJ刷题总计过千题。公众号：代码随想录，目前有8w+垂直程序员粉丝。

解析100+力扣原题，从容应对名企面试归纳经典算法面试题，总结经典算法的各个知识点分析多个算法应用场景，快速构建算法知识体系信息化和智能化对人类和世界的发展产生了巨大的影响，其中算法起着至关重要的作用。学习算法一直是计算机专业的学生感兴趣和头疼的事情，本书不像教科书一样过于理论，但又把用算法解决实际问题中所涉及的理论知识深入浅出地写出来，对广大读者来说这是一本非常值得研习的算法攻略。 王轩 哈工大计算学部副主任，哈工大(深圳)计算机科学与技术学院院长、教授，中国人工智能学会常务理事
如果说编程的内功是什么，那么一定是算法。所以我工作至今，依然保持学习算法的习惯。同时我也深感算法知识的庞杂，对于初学者来说，学习算法不是容易的事情。《代码随想录》这本书不仅抓住了算法的本质，帮助大家循序渐进地学习算法，而且从代码风格到性能分析都讲解到位，覆盖了面试中常见问题，值得大家一读。 王猛 百度智能云事业群组(ACG)技术委员会主席，百度云计算和大数据领域杰出架构师(T10)
一套稳定流畅运转的程序系统背后，选择高效合理的算法方案是关键，因此对算法能力的考察通常是技术面试时非常重要的一环。Carl的这本书系统地归纳了程序开发中常用的算法并对它们做了细致的讲解，不管是作为日常开发的工具书还是求职升阶的攻略书，都是不错的选择。

贺志强 腾讯天玑智趣工作室技术总监，T12级专家工程师
计算机专业无论是考研还是求职，数据结构与算法都是非常重要的内容，《代码随想录》系统性地讲解了数据结构与算法相关知识，做到了理论与实践并举，不仅适合程序员面试，同样可以帮助考研学子攻克初试与复试中数据结构与算法这一难关。 赵霖(@风华漫舞) 王道论坛创始人，王道考研系列图书主编

目录 第1章 准备面试要知己知彼 1 1.1 面试官为什么要考查算法 1 1.2 编程语言 2 1.2.1 学好算法之前更要学好编程语言 2 1.2.2 代码规范 2 1.3 如何写简历 5 1.3.1 简历模板 5 1.3.2 谨慎使用“精通” 5 1.3.3 拿不准的内容不要写在简历上 5 1.3.4 项目经验应该如何写 6 1.3.5 博客的重要 7 1.4 企业技术面试的流程 7 1.4.1 一面——机试面 7 1.4.2 二面——基础算法面 8 1.4.3 三面——综合技术面 8 1.4.4 四面——技术leader面 8 1.4.5 五面——HR面 9 1.5 本章小结 10 第2章 程序的能分析 11 2.1 时间复杂度分析 11 2.1.1 什么是时间复杂度 11 2.1.2 如何描述时间复杂度 12 2.1.3 递归算法的时间复杂度分析 14 2.2 程序的运行时间 17 2.2.1 超时是怎么回事 17 2.2.2 从硬件配置看计算机的能 18 2.2.3 测试计算机的运行速度 18 2.3 编程语言的内存管理 20 2.3.1 C 的内存管理 21 2.3.2 如何计算程序占用多少内存 22 2.3.3 内存对齐 22 2.4 空间复杂度分析 24 2.4.1 什么是空间复杂度 24 2.4.2 递归算法的空间复杂度分析 25 2.4.3 以空间换时间是常见的优化思路 32 2.5 本章小结 33 第3章 数组 34 3.1 数组理论基础 34 3.2 二分查找 36 3.2.1 二分法写法（一） 37 3.2.2 二分法写法（二） 38 3.3 移除元素 39 3.3.1 解法 40 3.3.2 双指针法 41 3.4 长度小的子数组 42 3.4.1 解法 42 3.4.2 滑动窗口 43 3.5 这个循环转懵了很多人 45 3.5.1 循环不变量 45 3.5.2 代码实现 46 3.6 本章小结 48 第4章 链表 49 4.1 链表理论基础 49 4.1.1 链表的类型 49 4.1.2 链表的存储方式 50 4.1.3 链表的定义 51 4.1.4 链表的操作 52 4.1.5 能分析 52 4.2 用虚拟头节点会方便得多 53 4.3 链表常见的六个操作 57 4.4 反转链表 60 4.4.1 双指针法 60 4.4.2 递归法 61 4.5 删除倒数第n个节点 62 4.6 环形链表 64 4.6.1 判断链表是否有环 65 4.6.2 寻找环的入口 66 4.7 本章小结 69 第5章 哈希表 70 5.1 哈希表理论基础 70 5.1.1 哈希函数 71 5.1.2 哈希碰撞 71 5.1.3 常见的三种哈希结构 73 5.2 有效的字母异位词 74 5.3 两个数组的交集 76 5.4 两数之和 78 5.5 四数相加 80 5.6 三数之和 81 5.6.1 哈希解法 81 5.6.2 双指针法 82 5.7 四数之和 85 5.8 本章小结 87 第6章 字符串 88 6.1 字符串与数组的区别 88 6.2 反转字符串 89 6.3 反转字符串II 90 6.4 反转字符串里的单词 92 6.5 KMP算法理论基础 96 6.5.1 什么是KMP算法 96 6.5.2 什么是前缀表 96 6.5.3 为什么要用前缀表 97 6.5.4 如何计算前缀表 98 6.5.5 时间复杂度分析 100 6.6 使用KMP匹配字符串 101 6.6.1 构造next数组 101 6.6.2 使用next数组做匹配 103 6.6.3 前缀表统一减一的代码实现 104 6.6.4 前缀表（不减一）的代码实现 105 6.7 找到重复的子字符串 107 6.8 本章小结 109 第7章 栈与队列 110 7.1 栈与队列理论基础 110 7.2 用栈组成队列 112 7.3 用队列组成栈 114 7.3.1 使用两个队列实现栈 115 7.3.2 使用一个队列实现栈 117 7.4 匹配括号 118 7.5 逆波兰表达式 120 7.6 滑动窗口值 122 7.7 前k个高频元素 126 7.8 接雨水 129 7.8.1 双指针解法 130 7.8.2 动态规划解法 132 7.8.3 单调栈解法 133 7.9 本章小结 137 第8章 二叉树 139 8.1 二叉树理论基础 139 8.1.1 二叉树的种类 139 8.1.2 二叉树的存储方式 141 8.1.3 二叉树的遍历方式 142 8.1.4 二叉树的定义 143 8.2 前中后序的递归遍历 144 8.3 前中后序的迭代遍历 146 8.3.1 前序遍历 146 8.3.2 中序遍历 147 8.3.3 后序遍历 148 8.4 前、中、后序统一迭代法 149 8.5 二叉树的层序遍历 152 8.6 反转二叉树 155 8.6.1 递归法 156 8.6.2 迭代法 156 8.7 对称二叉树 158 8.7.1 递归法 159 8.7.2 迭代法 162 8.8 二叉树的深度 164 8.8.1 递归法 165 8.8.2 迭代法 166 8.9 二叉树的小深度 167 8.9.1 递归法 168 8.9.2 迭代法 170 8.10衡二叉树 170 8.10.1 递归法 173 8.10.2 迭代法 175 8.11 二叉树的所有路径 176 8.11.1 递归法 177 8.11.2 迭代法 182 8.12 路和 183 8.12.1 递归法 183 8.12.2 迭代法 186 8.12.3 路和II 187 8.13 构造一棵二叉树 189 8.13.1 使用中序与后序遍历序列构造二叉树 189 8.13.2 使用前序与中序遍历序列构造二叉树 195 8.13.3 相关思考 197 8.14 合并两棵二叉树 197 8.14.1 递归 198 8.14.2 迭代法 200 8.15 在二叉搜索树中寻找节点 201 8.15.1 递归法 202 8.15.2 迭代法 203 8.16 验证二叉搜索树 204 8.16.1 递归法 205 8.16.2 迭代法 207 8.17 二叉搜索树的小差 208 8.17.1 递归法 208 8.17.2 迭代法 209 8.18 二叉搜索树中的众数 210 8.18.1 递归法 211 8.18.2 迭代法 215 8.19 二叉树公共祖先 216 8.19.1 普通二叉树 216 8.19.2 二叉搜索树 221 8.20 在二叉搜索树中插入一个节点 224 8.20.1 递归法 225 8.20.2 迭代法 227 8.21 在二叉搜索树中删除一个节点 228 8.21.1 递归法 228 8.21.2 迭代法 230 8.22 修剪二叉搜索树 231 8.22.1 递归法 232 8.22.2 迭代法 234 8.23 构造一衡二叉搜索树 235 8.23.1 递归法 236 8.23.2 迭代法 238 8.24 本章小结 239 第9章 回溯算法 240 9.1 回溯算法理论基础 240 9.1.1 什么是回溯算法 240 9.1.2 回溯法的能 240 9.1.3 回溯法可以解决的问题 240 9.1.4 如何理解回溯法 241 9.1.5 回溯法模板 241 9.2 组合问题 243 9.2.1 回溯算法 244 9.2.2 剪枝优化 248 9.3 组和（一） 250 9.3.1 回溯算法 251 9.3.2 剪枝优化 254 9.4 的字母组合 255 9.5 组和（二） 260 9.5.1 回溯算法 261 9.5.2 剪枝优化 263 9.6 组和（三） 265 9.7 分割回文串 270 9.8 复原IP地址 274 9.9 子集问题（一） 279 9.10 子集问题（二） 281 9.11 递增子序列 284 9.11.1 回溯算法 285 9.11.2 哈希优化 287 9.12 排列问题（一） 288 9.13 排列问题（二） 291 9.13.1 回溯算法 291 9.13.2 拓展 293 9.14 N皇后问题 296 9.15 解数独 301 9.15.1 回溯算法 302 9.15.2 判断棋盘是否合法 304 9.16 本章小结 305 第10章 贪心算法 306 10.1 贪心算法理论基础 306 10.1.1 什么是贪心 306 10.1.2 贪心的套路 306 10.2 分发饼干 307 10.3 摆动序列 309 10.4 子序和 312 10.5 买卖股票的时机II 314 10.6 跳跃游戏 316 10.7 跳跃游戏II 318 10.7.1 贪心解法（一） 320 10.7.2 贪心解法（二） 320 10.8 加油站 322 10.8.1 解法 323 10.8.2 贪心解法（一） 324 10.8.3 贪心解法（二） 325 10.9 分发糖果 327 10.10 柠檬水找零 330 10.11 用少数量的箭射爆气球 332 10.12 合并区间 335 10.13 单调递增的数字 338 10.13.1 解法 338 10.13.2 贪心解法 339 10.14 本章小结 340 第11章 动态规划 341 11.1 动态规划理论基础 341 11.1.1 动态规划题目的解题步骤 341 11.1.2 动态规划应该如何排查问题 342 11.2 斐波那契数 343 11.2.1 动态规划解法 344 11.2.2 递归解法 345 11.3 爬楼梯 346 11.4 使用花费爬楼梯 349 11.5 不同路径（一） 353 11.5.1 深度优先搜索 354 11.5.2 动态规划 355 11.5.3 数论方法 356 11.6 不同路径（二） 358 11.7 整数拆分 361 11.7.1 动态规划 362 11.7.2 贪心算法 364 11.8 不同的二叉搜索树 364 11.9 0-1理论基础 369 11.9.1 二维dp数组 370 11.9.2 一维dp数组 375 11.10 分割等和子集 379 11.11 目标和 382 11.12 一和零 385 11.13 理论基础 388 11.14 零钱兑换（一） 392 11.15 拼凑一个正整数 395 11.16 多步爬楼梯 398 11.17 零钱兑换（二） 399 11.18 方数 402 11.19 单词拆分 405 11.19.1 回溯算法 406 11.19.2 问题 407 11.20 买卖股票的时机 410 11.20.1 枚举 410 11.20.2 贪心算法 411 11.20.3 动态规划 411 11.21 买卖股票的时机II 414 11.22 买卖股票的时机III 416 11.23 买卖股票的时机IV 420 11.24 买卖股票时机（含冷冻期） 423 11.25 买卖股票的时机（含手续费） 426 11.26 长递增子序列 428 11.27 长连续递增序列 430 11.27.1 动态规划 430 11.27.2 贪心算法 432 11.28 长重复子数组 433 1

"归纳经典算法面试题，总结经典算法的各个知识点 分析多个算法应用场景，快速构建算法知识体系"