电子工业出版社-网上书店

本书归纳了程序员面试中的经典算法题，并按照由浅入深、循序渐进的顺序讲解。本书首先讲解程序员面试时需要了解的制作简历的技巧和IT名企的面试流程，以及面试时经常忽略的代码规范性问题。然后详细分析程序的时间复杂度和空间复杂库，包括如何把控程序的实际运行时间，以及编程语言的内存管理。接着讲解数组、链表、哈希表、字符串、栈与队列、二叉树、回溯算法、贪心算法、动态规划的理论基础及其相关题目。本书采用了力扣（LeetCode）的原题，方便读者在学习算法的同时，及时练习相关代码，加深对相关概念的理解。本书适合所有程序员阅读，特别是正在准备面试的程序员。希望本书可以帮助读者循序渐进地学习算法，并搭建起知识框架，提升算法功力。

目录


第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
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  本章小结

前言


算法是无数计算机先贤们的智慧结晶。当我们遇到生活中几乎无解的问题时，如果能利用相关算法，通过几行代码就可以轻松求出结果，那一刻将会感受到算法的美妙与神奇。
而我也被这一魔力所吸引。
十年前我开始学习算法，并且开始写与算法相关的博客。当时写算法博客的人还不多，网上能搜索到的算法文章也有限。
很多人没有写博客的习惯，因为写博客在一定程度上确实“耽误时间”。
不过当时我只是想记录下来，想着以后如果把这些知识都忘了，至少博客可以证明：曾经我掌握过。
没想到，算法陪伴我一晃就是十年，从本科到研究生，从一家公司到另一家公司，再到算法图书的出版……我的每一段人生经历都在从不同的角度和算法打交道。
随着多年学习和实践，我在各种在线判题平台上已经积累了上千题，对算法的理解已经有一套独特的体系。
同时我也发现，很多读者在刷题和学习算法时，真正的苦恼在于没有一套行之有效的刷题顺序。
例如，动态规划是公认的程序员面试里最难掌握的算法，也是出现频率最高的算法。如果仅仅讲解几道题目，即使再举一反三也远远达不到真正理解的程度。如果把动态规划的题目单纯地堆砌在一起，也只会让人越学越懵，陷入“一看就会，一写就废”的怪圈。讲清楚一两道题容易，但把整个动态规划的各个分支讲清楚，把每道题目讲透彻，并用一套方法论来指导就有难度了。这既是我无数日夜地伏案思考、反复推理，要帮助读者解决的问题，也是本书的使命所在。
对于动态规划、二叉树、回溯算法等，本书都总结了一套行之有效的方法论，系统性地解决这些算法的相关问题，并把相关题目按照由易到难的顺序编排，让读者循序渐进地征服算法的一座又一座高山。
本书特色
刚开始学习数据结构与算法，或者在力扣（LeetCode）上刷题的读者都有这种困惑——从何学起，先学什么，再学什么。很多人刷题的效率低，主要体现在以下三点：
?难以寻找适合自己的题目。
?找到了不合适现阶段做的题目，结果发现毫无头绪。
?没有全套的优质题解可以参考。
我相信很多人对此深有体会，所以我将每一个专题中的题目按照由易到难的顺序进行编排，每一道题目所涉及的知识都会有相应的题目做知识铺垫，做到环环相扣。
建议读者按章节顺序阅读本书，在阅读的过程中会发现题目编排上的良苦用心。
本书不仅在题目编排上精心设计，而且在针对读者最头痛的算法问题上做了详细且深入的讲解。
关于动态规划，都知道递归公式的重要性，但dp数组的含义、dp数组的初始化、遍历顺序都很重要。例如，解决背包问题时，遍历顺序才是最关键的也是最难理解的。
关于回溯算法，不同集合之间需要去重。虽然各种资料都说要去重，但没有说清楚是“树层去重”还是“树枝去重”——这是我为了说明去重的过程而创造的两个词汇。
关于KMP算法，都知道使用next数组进行回退，可根据前缀表生成next数组有很多种方式，却没有说清楚，导致大家看得一头雾水。
关于二叉树，不同的遍历顺序的递归函数究竟如何安排，递归函数什么时候需要返回值，什么时候不用返回值，这些细节都决定了对二叉树的理解是否到位。
本书同时针对每一个专题的特点，整理出其通用的解法套路。例如，在二叉树专题中，总结了递归“三部曲”来帮助读者掌握二叉树中各种遍历方式的写法。回溯算法中的回溯“三部曲”可以帮助读者理解回溯算法晦涩难懂的过程。动态规划中的动规“五部曲”可以帮助读者在一套思考框架下解决所有的动态规划题目。
相信读者耐心看完本书，会对书中介绍的算法有更深层次的理解。
本书配套资源
本书统一使用C++语言进行讲解，对于使用其他语言的读者，可以浏览本书配套网站：programmercarl（com域名）——支持Java、Python、Go、JavaScript等多语言版本，同时一些题目还有动画演示，帮助读者更好地掌握本书内容。
在微信公众号“代码随想录”后台回复“算法学习”，可以加入算法学习交流群，并且获得本书配套学习资料，包含代码、题目大纲等。
我会在B站“代码随想录”定期更新算法视频，相信可以帮助读者更好地理解相关知识。
勘误
个人能力有限，书中难免有疏漏之处，恳请广大读者们批评指正。
在微信公众号“代码随想录”底部的一个菜单中有我的联系方式，如果读者有疑问或者发现了Bug，可以与我联系，我会一一回复。同时我在公众号添加了一个新的菜单入口，更新书中的Bug。
致谢
这里要感谢录友们（“代码随想录”的朋友们，也是公众号“代码随想录”的忠实读者），是你们的支持，让“代码随想录”从无到有，到最后出版成书与读者见面。虽然从未谋面，但通过文字，我们已经交流了整整一年有余。真心地感谢每一位录友。
感谢电子工业出版社的工作人员，特别是陈晓猛编辑。陈编辑认真负责，是非常可靠的合作伙伴。
最后我要感谢我的父母——孙世忠先生和马丽丽女士。我的家乡在黑龙江偏远小镇，父亲长期从事重体力劳动，辛勤劳苦，母亲操持家业，督促我学习。父母在我求学的路上给予了我最大的支持，付出了非常多。我无以为谢，谨以此书献给他们。

孙秀洋（@程序员Carl）
2021年10月11日于深圳南山

本书配套资源下载

对不起，暂无音视频资源！

代码随想录——跟着Carl学算法