程序员面试算法宝典

这是一本讲解程序员面试算法的书。在写法上，除了讲解如何解答算法问题外，还引入了例子辅以说明，让读者能更容易理解。
本书将程序员面试笔试过程中各类算法类真题一网打尽。在题目的广度上，通过各种渠道，搜集了近3年来多家IT企业面试算法高频题目；在题目的深度上，本书由浅入深、庖丁解牛式地分析每一个题目，并提炼归纳，同时，引入例子与源代码、时间复杂度与空间复杂度的分析。本书根据真题所属知识点分门别类，结构合理，条理清晰，对于读者进行学习与查阅意义重大。
本书是针对计算机相关专业毕业生面试笔试的求职用书，也可以作为本科生、研究生学习数据结构与算法的辅导书，同时也适合期望在计算机行业大显身手的计算机爱好者阅读。

适读人群 ：本书是针对计算机相关专业毕业生面试笔试的求职用书
在这里，有面试笔试常见技巧的提炼与总结；
在这里，有面试笔试高频算法知识点的整理与剖析；
在这里，有面试笔试历年算法真题的解答与拓展。

计算机技术博大精深，而且日新月异，Hadoop、GPU计算、移动互联网、模式匹配、图像识别、神经网络、蚁群算法、大数据、机器学习、人工智能、深度学习等新技术让人眼花缭乱，稍有不慎，就会被时代抛弃。于是，很多IT从业者开始困惑了，不知道从何学起，到底什么才是计算机技术的基石。其实，究其本质还是最基础的数据结构与算法知识：Hash、动态规划、分治、排序、查找等。所以，无论是世界级的大型企业还是几个人的小公司，在面试求职者的时候，往往都会考察这些最基础的知识，无论你的研究方向是什么，这些基础知识都应该熟练掌握。
本书正是从这些基础知识点出发，讲解了求职过程中常见的数据结构与算法的真题，从而让求职者能轻松应对算法类的面试笔试题目。本书对于算法的讲解，不仅使用图文并茂的方式，而且还辅以示例的讲解，目的就是为了使读者更容易读懂。为了能够写出精品书籍，我们对每一个技术问题都反复推敲，与算法大牛一起反复论证可行性；对文字，我们更是咬文嚼字，字斟句酌。所有这些付出，只为让读者能够在读完本书后有所收获。
虽然市面上同类型书籍很多，也都写得不错，但是我们相信，我们能够写出更适合读者胃口的高质量精品书籍。为了能够在有限的篇幅里面尽可能地全是“干货”，在题目的选择上也下了很多功夫：首先，通过搜集近3年以来几乎所有IT企业的面试笔试算法真题，包括已经出版的其他著作、技术博客、在线编码平台、刷题网站等，保证所选样本足够大。其次，我们选择题目的时候，尽可能不选择那种一眼就能知道结果的简单题，也没有选择那种怪题、偏题和很难的题，我们选题原则是难度适中或者看上去简单但实际并不容易。通过我们的努力，力求所选出来的算法真题能够最大限度地帮助读者。在真题的解析上，我们采用层层递进的写法，先易后难，层层深入，将问题抽丝剥茧，使得读者能够跟随我们的思路，一步步找到问题的最优解。
写作的过程是一个自我提高、自我认识、自我救赎的过程，很多知识，只有深入理解与剖析后，你才能领悟其中的精髓，掌握其中的技巧，程序员求职算法也不例外。本书不仅具备了其他书籍分析透彻、代码清晰合理的优点，还具备以下几个方面的优势：
第一，本套书籍分多种语言版本实现：C/C++、Java、C#、Python、PHP、Javascript、Kotlin、Go等，这样，无论读者侧重于哪一种语言，都能够有适合自己的书。本书中如果没有特别强调，代码实现均默认使用C/C++语言。
第二，每个题目除了循序渐进的分析以外，还对方法进行了详细阐述，针对不同方法的时间复杂度与空间复杂度，都进行了详细分析。除此之外，为了更具说服力，每一种方法几乎都对应有示例讲解辅以说明，对方法是一种更好的辅助。
第三，代码较为规范，完全参照华为编程规范、Google编程规范。小作坊编码的时代早已过去，程序员要想在一个团队中大展拳脚，就离不开合作，而合作的基础就是共同遵循统一的编码规范。不仅如此，规范化的编码往往有助于读者理解代码。
第四，除了对题目的讲解，还有部分触类旁通的题目供读者练习。本书不可能将所有的程序员求职类的数据结构与算法类题目囊括，但会尽可能地对一些常见的求职类算法题、具有代表性的算法题重点讲解，将其他一些题目以练习题的形式展现在读者面前，以供读者思考与学习。
本书中有部分思想来源于网络上的无名英雄，无法追踪到最原始的出处，在此对这些幕后英雄致以最崇高的敬意。没有学不好的学生，只有教不好的老师，我们希望无论是什么层次的学生，都能毫无障碍地看懂书中所讲内容。如果读者存在求职困惑或是对本书中的内容存在异议，都可以通过[email protected]联系作者。

猿媛之家

前言
面试笔试经验技巧篇
经验技巧1 如何巧妙地回答面试官的问题？2
经验技巧2 如何回答技术性的问题？3
经验技巧3 如何回答非技术性问题？4
经验技巧4 如何回答快速估算类问题？5
经验技巧5 如何回答算法设计问题？6
经验技巧6 如何回答系统设计题？9
经验技巧7 如何解决求职中的时间冲突问题？11
经验技巧8 如果面试问题曾经遇见过，是否要告知面试官？12
经验技巧9 在被企业拒绝后是否可以再申请？13
经验技巧10 如何应对自己不会回答的问题？13
经验技巧11 如何应对面试官的“激将法”语言？14
经验技巧12 如何处理与面试官持不同观点这个问题？15
经验技巧13 什么是职场暗语？15
面试笔试真题解析篇
第1章 链表21
1.1 如何实现链表的逆序21
1.2 如何从无序链表中移除重复项27
1.3　如何计算两个单链表所代表的数之和30
1.4　如何对链表进行重新排序34
1.5　如何找出单链表中的倒数第k个元素37
1.6　如何检测一个较大的单链表是否有环41
1.7　如何把链表相邻元素翻转44
1.8　如何把链表以K个结点为一组进行翻转46
1.9　如何合并两个有序链表49
1.10　如何在只给定单链表中某个结点的指针的情况下删除该结点52
1.11　如何判断两个单链表（无环）是否相交54
1.12　如何翻转变异的链表58
1.13　如何展开链接列表59
第2章　 栈、队列与哈希63
2.1　如何实现栈63
2.2　如何实现队列69
2.3　如何翻转栈的所有元素75
2.4　如何根据入栈序列判断可能的出栈序列79
2.5　如何用O(1)的时间复杂度求栈中最小元素81
2.6　如何用两个栈模拟队列操作83
2.7　如何设计一个排序系统84
2.8　如何实现LRU缓存方案86
2.9 如何从给定的车票中找出旅程90
2.10　如何从数组中找出满足a+b=c+d的两个数对92
第3章　 二叉树94
3.1　二叉树基础知识94
3.2　如何把一个有序整数数组放到二叉树中96
3.3 如何从顶部开始逐层打印二叉树结点数据98
3.4 如何求一棵二叉树的最大子树和100
3.5 如何判断两棵二叉树是否相等102
3.6 如何把二叉树转换为双向链表104
3.7 如何判断一个数组是否为二元查找树后序遍历的序列106
3.8 如何找出排序二叉树上任意两个结点的最近共同父结点108
3.9 如何复制二叉树113
3.10 如何在二叉树中找出一条路径满足路径上所有结点的和等于给定的整数114
3.11 如何对二叉树进行镜像反转116
3.12 如何在二叉排序树中找出第一个大于中间值的结点117
3.13 如何在二叉树中找出路径和的最大值119
3.14 如何实现反向DNS查找缓存121
第4章 数组125
4.1 如何找出数组中唯一的重复元素125
4.2 如何查找数组中元素的最大值和最小值131
4.3 如何找出旋转数组的最小元素135
4.4 如何找出数组中丢失的数138
4.5 如何找出数组中出现奇数次的数140
4.6 如何找出数组中第k小的数142
4.7 如何求数组中两个元素的最小距离145
4.8 如何求解最小三元组距离148
4.9 如何求数组中绝对值最小的数152
4.10 如何求数组连续最大和155
4.11 如何找出数组中出现一次的数158
4.12 如何在不排序的情况下求数组中的中位数160
4.13 如何求集合的所有非空子集162
4.14 如何对数组进行循环移位166
4.15 如何在有规律的二维数组中进行高效的数据查找168
4.16 如何寻找最多的覆盖点170
4.17 如何判断请求能否在给定的存储条件下完成171
4.18 如何按要求构造新的数组174
4.19 如何获取最好的矩阵链相乘方法175
4.20 如何求解迷宫问题177
4.21 如何从三个有序数组中找出它们的公共元素180
4.22 如何对有大量重复数字的数组排序181
第5章 字符串187
5.1 如何求一个字符串的所有排列187
5.2 如何求两个字符串的最长公共子串192
5.3 如何对字符串原地压缩195
5.4 如何对字符串进行反转197
5.5 如何判断两个字符串是否互为换位字符串199
5.6 如何判断两个字符串的包含关系201
5.7 如何对由大小写字母组成的字符串排序204
5.8 如何消除字符串的内嵌括号206
5.9 如何判断字符串是否为整数207
5.10 如何实现字符串的匹配210
5.11 如何求字符串里的最长回文子串214
5.12 如何按照给定的字母序列对字符串排序220
5.13 如何判断一个字符串是否包含重复字符223
5.14 如何删除给定字符串中的指定字符225
5.15 如何找到由其他单词组成的最长单词227
5.16 如何统计字符串中连续的重复字符个数230
5.17 如何求最长递增子序列的长度231
5.18 如何对字符串进行旋转232
5.19 如何求解字符串的最长重复子串233
5.20 如何求解字符串中字典序最大的子序列238
5.21 如何判断一个字符串是否由另外一个字符串旋转得到240
5.22 如何去掉字符串的首尾空格并合并多个连续空格为一个241
5.23 如何求字符串的编辑距离243
5.24 如何求相对路径245
5.25 如何查找到达目标词的最短链长度247
第6章 基本数字运算250
6.1 如何判断一个自然数是否为某个数的平方250
6.2 如何判断一个数是否为2的n次方252
6.3 如何不使用除法操作符实现两个正整数的除法254
6.4 如何