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

本书全面、系统地总结了在准备程序员面试过程中必备的数据结构与算法。本书首先详细讨论整数、数组、链表、字符串、哈希表、栈、队列、二叉树、堆和前缀树等常用的数据结构，然后深入讨论二分查找、排序、回溯法、动态规划和图搜索等算法。除了介绍相应的基础知识，每章还通过大量的高频面试题系统地总结了各种数据结构与算法的应用场景及解题技巧。本书适合所有正在准备面试的程序员阅读。无论是计算机相关专业的应届毕业生还是初入职场的程序员，本书总结的数据结构和算法的基础知识及解题经验都不仅可以帮助他们提高准备面试的效率，还可以增加他们通过面试的成功率。

第1章  整数	1
1.1  整数的基础知识	1
1.2  二进制	4
1.3  本章小结	13
第2章  数组	14
2.1  数组的基础知识	14
2.2  双指针	15
2.3  累加数组数字求子数组之和	22
2.4  本章小结	28
第3章  字符串	30
3.1  字符串的基础知识	30
3.2  双指针	31
3.3  回文字符串	41
3.4  本章小结	45
第4章  链表	46
4.1  链表的基础知识	46
4.2  哨兵节点	47
4.3  双指针	50
4.4  反转链表	58
4.5  双向链表和循环链表	66
4.6  本章小结	71
第5章  哈希表	73
5.1  哈希表的基础知识	73
5.2  哈希表的设计	74
5.3  哈希表的应用	82
5.4  本章小结	91
第6章  栈	92
6.1  栈的基础知识	92
6.2  栈的应用	93
6.3  本章小结	108
第7章  队列	109
7.1  队列的基础知识	109
7.2  队列的应用	110
7.3  二叉树的广度优先搜索	114
7.4  本章小结	125
第8章  树	126
8.1  树的基础知识	126
8.2  二叉树的深度优先搜索	127
8.3  二叉搜索树	141
8.4  TreeSet和TreeMap的应用	153
8.5  本章小结	160
第9章  堆	161
9.1  堆的基础知识	161
9.2  堆的应用	165
9.3  本章小结	172
第10章  前缀树	174
10.1  前缀树的基础知识	174
10.2  前缀树的应用	179
10.3  本章小结	191
第11章  二分查找	192
11.1  二分查找的基础知识	192
11.2  在排序数组中二分查找	193
11.3  在数值范围内二分查找	201
11.4  本章小结	205
第12章  排序	206
12.1  排序的基础知识	206
12.2  计数排序	208
12.3  快速排序	211
12.4  归并排序	215
12.5  本章小结	222
第13章  回溯法	224
13.1  回溯法的基础知识	224
13.2  集合的组合、排列	226
13.3  回溯法解决其他类型问题	235
13.4  本章小结	239
第14章  动态规划	241
14.1  动态规划的基础知识	241
14.2  单序列问题	248
14.3  双序列问题	266
14.4  矩阵路径问题	281
14.5  背包问题	293
14.6  本章小结	303
第15章  图	305
15.1  图的基础知识	305
15.2  图的搜索	307
15.3  拓扑排序	333
15.4  并查集	342
15.5  本章小结	354

前  言

2021年1月22日，我从工作超过10年的微软离职，并于23日入职Rubrik，一家相对而言规模要小很多的公司，开始一段新的职业旅程。
与所有程序员一样，换公司工作我也需要经历一轮又一轮的面试，而算法面试是面试中的重头戏。这次换工作的准备与面试阶段正好与本书的撰写阶段重合。在此之前，我作为面试官在微软已经面试了很多应聘者。在撰书的过程中，我结合自己多年来被他人面试及面试他人的经验，一直在思考如何高效地学习数据结构和算法，如何在面试短短的几十分钟内快速找到解题思路并写出高质量的代码。
以这十几年对程序员面试这个领域的观察，我的结论是面试的难度在逐年增加，准备面试需要花费的时间和精力也越来越多。几年前如果听说谁为了准备面试刷了200道算法题，大家都会觉得非常惊讶。现在每个应聘者都在刷题，应届毕业生准备面试刷400道算法题基本上只能算是起步。由于应聘者刷题越来越熟练，程序员面试的标准自然也随之水涨船高。
我个人不喜欢也不建议采用题海战术。我们真正需要的是系统学习并深刻理解不同数据结构和算法的特征及适用场景。在真正掌握了每个数据结构及算法的精髓之后，如果针对典型的面试题进行必要的练习，那么在面试时就能以不变应万变，不管遇到什么样的面试题都能迎刃而解。帮助读者系统学习并深刻理解不同数据结构和算法的特征及适用场景，是我撰写本书的初衷；帮助读者在算法面试中能快速找到解题思路并写出高质量的代码，是我撰写本书的目的。
学习数据结构，需要先熟练掌握插入、删除和查找等基本操作，这些基本操作往往是解决很多面试题的关键。例如，如果我们熟练掌握了前缀树的插入和查找操作，那么很多与字符串前缀相关的问题都很容易解决。
同样，对于基础算法我们也需要深刻理解它们的原理及其实现代码。例如，二分查找通常只需要10行左右的代码就能实现，我们要理解它的循环条件的比较运算符什么时候是“＜”，以及什么时候是“＜=”，确定下一步查找前半部分或后半部分的标准是什么。理解了这些原理之后，不管面试题如何变化，最终解决问题的代码都大同小异。
学习数据结构，还要深刻理解每种数据结构的特点及其适用场景，这样才能在面试过程中合理选择数据结构解决问题。例如，哈希表是时间效率非常高的数据结构，它的插入、删除和查找操作的时间复杂度都是O(1)。虽然哈希表的时间效率非常高，但并不是所有的问题都能用哈希表来解决。如果存储的元素是字符串，并且需要根据字符串的前缀进行查找，那么前缀树是更好的选择。如果存储的元素是数字，并且解决问题需要知道数据集合中的最大值或最小值，那么堆可能是更好的选择。如果需要对动态数据集合排序，并且需要根据数值的大小进行查找，那么平衡的二叉搜索树（Java中的TreeSet或TreeMap）可能是更好的选择。
同样，学习算法也要理解每种算法的特点及其适用场景。例如，回溯法和动态规划适合解决的问题看起来很类似。如果解决一个问题需要多个步骤，并且每个步骤都面临多个原则，那么我们可以考虑使用回溯法或动态规划来解决这个问题。如果要求列举出问题所有的解，那么我们应该采用回溯法来解决问题。如果只是要求计算某个最优解（通常是最大值或最小值）或计算解的数目，那么我们应该采用动态规划来解决问题。
本书的关注点是算法面试，因此，和常规的算法类书籍相比，本书更加注重准备面试的实用性。本书注重总结常用的解题思路。例如，如果面试题提到与二叉树层相关的概念，那么我们可以尝试用广度优先搜索算法来解决这个问题。本书“解题小经验”条目总结了常用的解题思路，建议读者留意。
本书还着重总结了一些常用的代码模板，希望读者能够理解这些代码模板的来龙去脉，这样在面试中如果遇到类似的问题就能套用相应的模板解决，轻松做到举一反三。例如，用并查集解决问题时合并和查找操作的代码大同小异，在合适的时候套用函数union和findFather就能解决很多与图相关的问题。
在撰写本书的过程中我得到了很多朋友的帮助。类似于程序员在递交代码之前需要通过代码审查，在将书稿交付给出版社编辑修改、排版之前，我邀请了很多朋友帮忙审阅，其中包括微软的陈黎明、贾志勇、王洪臣（Walter Wang）、高天翔（Frank Gao）、袁源、李兴华，谷歌的田超，脸书的董朝、何涛，苹果的吴斌，阿里巴巴的韩伟东、殷焰，字节跳动的尹彦，以及诺基亚贝尔的吴永康等。他们仔细审阅了书稿并提出大量建议，大幅度提高了本书的质量。在此谨向他们表示由衷的感谢。
当然，我的时间和能力有限，书中难免存在一些疏漏之处。如果读者发现书中的问题，请通过电子邮件（zhedahht@hotmail.com）和我联系。
感谢电子工业出版社的工作人员，尤其是张春雨的帮助。他们大到全书的构架，小到文字的推敲，都给予了我极大的帮助，从而使本书的质量得到了极大的提升。
本书还得到了很多朋友的支持和帮助，由于篇幅有限，在此不一一列举，但我一样对他们心存感激。
最后，我要衷心地感谢我的爱人刘素云。感谢她多年来对我的理解和支持，为我营造了一个温馨而又浪漫的家，让我能够静下心来读书和写作。我也同样感谢我们两个可爱的儿子，他们脸上纯真、灿烂的笑容是我每天工作的动力。我无以为谢，谨以此书献给他们。


何海涛         
2021年1月24日于西雅图

本书配套资源下载

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

剑指Offer（专项突破版）：数据结构与算法名企面试题精讲