本文是我自己在秋招复习时的读书笔记，整理的知识点，也是为了防止忘记，尊重劳动成果，转载注明出处哦！如果你也喜欢，那就点个小心心，文末赞赏一杯豆奶吧，嘻嘻。 让我们共同成长吧……
面试手撕算法经典题目（67道）
第1章 面试的流程
1.1 面试官谈面试
重点：算法、数据结构、专业技能、项目经验
1.2 面试的三种形式
电话面试、共享桌面远程面试、现场面试
1.3 面试的三个环节
行为面试、技术面试、应聘者提问
项目经验描述：采用STAR模型（Situation：简短介绍项目背景；Task：自己完成的任务；Action：为了完成任务做了哪些工作；Result：自己的贡献是什么）
应聘者掌握技能程度：了解、熟悉、精通
应聘者提问：提问与招聘职位和项目相关的问题。相应职位应该掌握哪些技能，我应该怎么提前准备？对于该岗位有没有相关的技能培训？
第2章 面试需要的基础知识
2.1 面试官谈基础知识
编程语言、算法与数据结构、操作系统等
2.2 编程语言
面试题1：赋值运算函数
面试题2：实现Singleton模式
题目：设计一个类，我们只能生成该类的一个实例。
2.3 数据结构
数据结构是面试的重点，一般围绕数组、字符串、链表、树、栈以及队列
面试题3：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：从右上角或左下角开始找，逐行删除，或者用二分法查找
面试题4：替换空格
题目：实现一个函数，把一个字符串中的空格替换成“%20”。 例如输入“We Are Happy.”，则输出“We%20Are%20Happy.”。
思路：从后往前复制，数组长度会增加，或使用StringBuilder、StringBuffer类
面试题5：从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印链表每个节点的值。
思路：借助栈实现，或使用递归的方法。
面试题6：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：先找出根节点，然后利用递归方法构造二叉树
面试题7：用两个栈实现队列
题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：一个栈压入元素，而另一个栈作为缓冲，将栈1的元素出栈后压入栈2中。也可以将栈1中的最后一个元素直接出栈，而不用压入栈2中再出栈。
2.4 算法和数据操作
面试题8：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
思路：利用二分法，找到中间的数，然后和最左边的值进行比较，若大于最左边的数，则最左边从mid开始，若小于最右边值，则最右边从mid开始。若左中右三值相等，则取mid前后值中较小的数。
面试题9：斐波那契数列
题目：现在要求输入一个整数n，输出斐波那契数列的第n项。n<=39
思路：递归的效率低，使用循环方式。
引申1： 跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
引申2：变态跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
引申3：矩阵覆盖
题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：斐波那契数列思想
面试题10：二进制中1的个数
题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：a&(a-1)的结果会将a最右边的1变为0，直到a = 0，还可以先将a&1 != 0，然后右移1位，但不能计算负数的值，
第3章 高质量的代码
3.1 面试官谈代码质量
3.2 代码的规范性
规范的代码：清晰的书写、清晰的布局、合理的命名
3.3 代码的完整性
完整的代码：功能测试、边界测试、负面测试
面试题11： 数值的整数次方
题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不得使用库函数，不需要考虑大数问题
思路：不能用==比较两个浮点数是否相等，因为有误差。考虑输入值的多种情况。
面试题12：打印1到最大的n位数
题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如，输入3，则打印出1、2、3 …… 999
思路：考虑大数问题，使用字符串或数组表示。
面试题13：O(1)时间删除链表节点
题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。
思路：将要删除节点的下一个节点的值赋给要删除的节点，然后指向下下一个节点。
面试题14：调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变
思路：每次只和前面一个数交换位置。或者利用辅助数组
面试题15：链表中倒数第k个结点
扩展题：找中间节点，使用两个指针，一个走一步，一个走两步。找到中间节点
思路：定义一快一慢两个指针，快指针走K步，然后慢指针开始走，快指针到尾时，慢指针就找到了倒数第K个节点。
面试题16：反转链表
题目：输入一个链表，反转链表后，输出链表的所有元素。
扩展题：输出反转后链表的头节点，定义三个指针反向输出。
思路：定义两个指针，反向输出
面试题17： 合并两个排序的链表
题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：递归与非递归求解，小数放在前面。
面试题18：树的子结构
题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：若根节点相等，利用递归比较他们的子树是否相等，若根节点不相等，则利用递归分别在左右子树中查找。
第4章 解决面试题的思路
4.1 面试官谈思路
4.2 画图让抽象问题形象化
面试题19：二叉树的镜像
题目：给定一个二叉树，输出该二叉树的镜像。
思路：使用递归或非递归方式交换每个节点的左右子树位置。
面试题20：顺时针打印矩阵
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如，如果输入如下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路：终止行号大于起始行号，终止列号大于起始列号。
4.3 举例让抽象问题具体化
面试题21：包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1).
思路：定义两个栈，一个存放入的值。另一个存最小值。
面试题22：栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：用栈来压入弹出元素，相等则出栈。
面试题23：从上往下打印二叉树
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：利用队列（链表）辅助实现。
面试题24： 二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出true,否则输出false。假设输入的数组的任意两个数字都互不相同。
思路：先找到右子树的开始位置，然后分别进行左右子树递归处理。
面试题25：二叉树中和为某一值得路径
题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路：先保存根节点，然后分别递归在左右子树中找目标值，若找到即到达叶子节点，打印路径中的值
面试题26：复杂链表的复制
题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：先复制链表的next节点，将复制后的节点接在原节点后，然后复制其它的节点，最后取偶数位置的节点（复制后的节点）。
面试题27：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：定义一个链表的尾节点，递归处理左右子树，最后返回链表的头节点
面试题28：字符串的排列
题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：将当前位置的字符和前一个字符位置交换，递归。
第5章 优化时间和空间效率
5.1 面试官谈效率
5.2 时间效率
面试题29：数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字
思路：将首次出现的数count+1，与之后的数进行比较，相等则+1，否则—1，最后进行校验是否超过长度的一半。
面试题30：最小的k个数
题目：输入n个整数，找出其中最小的K个数。
思路：先将前K个数放入数组，进行堆排序，若之后的数比它还小，则进行调整
面试题31：连续子数组的最大和
题目：求连续子数组（包含负数）的最大和
思路：若和小于0，则将最大和置为当前值，否则计算最大和。
面试题32：从1到整数n中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如 输入12，从1到12这些整数中包含1的数字有1,10,11,和12,1一共出现了5次。
思路：若百位上数字为0，百位上可能出现1的次数由更高位决定；若百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响；若百位上数字大于1，则百位上出现1的情况仅由更高位决定
面试题33：把数组排成最小数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个
思路：先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。或使用比较和快排的思想，将前面的数和最后的数比较，若小则放到最前面，最后再递归调用。
5.3 时间效率与空间效率的平衡
面试题34：丑数
题目：丑数是只包含因子2、3和5的数，求从小到大的第N个丑数。习惯性把1作为第一个丑数。
思路：乘2或3或5，之后比较取最小值。
面试题35：第一个只出现一次的字符
题目：在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
思路：利用LinkedHashMap保存字符和出现次数。
面试题36：数组中的逆序对
题目：数组中的两个数字，如果前一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P
思路：本质是归并排序，在比较时加入全局变量count进行记录逆序对的个数，若data[start] >= data[index] ，则count值为mid+1-start
面试题37：两个链表的第一个公共节点
题目：输入两个链表，找出它们的第一个公共结点。
思路：先求出链表长度，然后长的链表先走多出的几步，然后两个链表同时向下走去寻找相同的节点，代码量少的方法需要将两个链表遍历两次，然后从头开始找相同的节点。
第6章 面试中的各项能力
6.1 面试官谈能力
6.2 沟通能力和学习能力
6.3 知识迁移能力
面试题38：数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4.
思路：利用二分查找+递归思想，进行寻找。当目标值与中间值相等时进行判断
面试题39：二叉树的深度
题目：输入一棵二叉树的根节点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路：利用递归遍历分别返回左右子树深度
引申：
题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路：平衡因子的绝对值<= 1.
面试题40：数组中只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：两个相同的数异或后为0，将所有数异或后得到一个数，然后求得1在该数最右边出现的index，然后判断每个数右移index后是不是1。
面试题41：和为s的两个数字 VS 和为s的连续正数序列
题目1：输入一个递增排序的数组和一个数字s，在数组中查找两个数，是的他们的和正好是s，如果有多对数字的和等于s，输出两个数的乘积最小的。
思路：定义两个指针，分别从前面和后面进行遍历。间隔越远乘积越小，所以是最先出现的两个数乘积最小
题目2：输出所有和为s的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
思路：定义两个指针，分别递增，寻找和为s的序列。
面试题42：翻转单词顺序 VS 左旋转字符串
题目1：翻转字符串
思路：先将整个字符串翻转，然后将每个单词翻转。
题目2：左旋转字符串。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出
思路：拼接或反转三次字符串
6.4 抽象建模能力
面试题43：n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s,输入n,打印出s的所有可能出现的概率
思路：递归一般是自顶向下的分析求解，而循环则是自底向上，占用更少的空间和更少的时间，性能较好。定义一个二维数组，第一次掷骰子有6种可能，第一个骰子投完的结果存到probabilities[0]；第二次开始掷骰子，在下一循环中，我们加上一个新骰子，此时和为n的骰子出现次数应该等于上一次循环中骰子点数和为n-1,n-2,n-3, n-4,n-5，n-6的次数总和，所以我们把另一个数组的第n个数字设为前一个数组对应n-1,n-2,n-3,n-4,n-5，n-6之和
面试题44：扑克牌的顺子
题目：从扑克牌中随机抽取5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
思路：用数组记录五张扑克牌，将数组调整为有序的，若0出现的次数>=顺子的差值，即为顺子。
面试题45：圆圈中最后剩下的数字 （约瑟夫环）
题目：0,1,……,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
思路：利用循环链表实现
6.5 发散思维能力
面试题46：求1+2+……+n
题目：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：巧用递归（返回值类型为Boolean）
面试题47：不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：利用位运算
面试题48：不能被继承的类
思路：私有构造器的类不能继承（final）
第7章 两个面试案例
面试题49：把字符串转换成整数
题目：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
思路：若为负数，则输出负数，字符0对应48,9对应57，不在范围内则返回false。
面试题50： 求树中两个节点的最低公共祖先
1）树是二叉搜索树
思路：从树的根节点开始遍历，如果根节点的值大于其中一个节点，小于另外一个节点，则根节点就是最低公共祖先。否则如果根节点的值小于两个节点的值，则递归求根节点的右子树，如果大于两个节点的值则递归求根的左子树。如果根节点正好是其中的一个节点，那么说明这两个节点在一条路径上，所以最低公共祖先则是根节点的父节点，时间复杂度是O(logn)，空间复杂度是O(1)
2）若树是普通树，但有指向父节点的指针
思路：两个节点如果在两条路径上，类似于求两个链表的第一个公共节点。由于每个节点的深度最多为logn，所以时间复杂度为O(logn),空间复杂度O(1)
3）若树是普通树，并没有指向父节点的指针
思路：用栈来实现类似于指向父节点指针的功能，获取node节点的路径时间复杂度为O(n),所以总的时间复杂度是O(n),空间复杂度是O(logn)
第8章 英文版新增面试题
8.1 数组
面试题51：数组中重复的数字
题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内，找出数组中任意一个重复的数字
思路：若下标大于length，则减去length，最后再加上length，若下标的数组值大于length，则返回true。或使用辅助空间（HashSet）
面试题52：构建乘积数组
题目：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。其中A[i] = 1。不能使用除法，
思路：使用矩阵法求解，将矩阵分为上三角矩阵和下三角矩阵，分别求乘积
8.2 字符串
面试题53：正则表达式匹配
题目：请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）
思路：当字符串只有一个字符时，进行判断，否则就有两种递归情况，（1）当模式中的第二个字符不是“”时：如果字符串第一个字符和模式中的第一个字符相匹配或是点那么字符串和模式都后移一个字符，然后匹配剩余的；如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。（2）当模式中的第二个字符是“”时：如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配；如果字符串第一个字符跟模式第一个字符匹配或是点，可以有3种匹配方式：1 >模式后移2字符，相当于x*被忽略；2>字符串后移1字符，模式后移2字符；3>字符串后移1字符，模式不变，即继续匹配字符下一位，因为 * 可以匹配多位；
面试题54：表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）
思路：逐个字符进行判断，e或E和小数点最多出现一次，而e或E的前一个必须是数字，且不能是第一个或最后一个字符，符号的前一个字符不能是e或E。也可用正则表达式判断！
面试题55：字符流中第一个不重复的字符
题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
思路：借助辅助空间进行判断，如字符数组。
8.3 链表
面试题56：链表中环的入口
题目：一个链表中包含环，请找出该链表的环的入口结点。
思路：定义快慢两个指针，相遇后（环中相汇点）将快指针指向pHead 然后一起走，每次往后挪一位，相遇的节点即为所求。详细分析：相遇即p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
面试题57：删除链表中重复的结点
题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
思路：先新建一个头节点，然后向后查找值相同的节点，重复查找后删除
8.4 树
面试题58: 二叉树的下一个结点
题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：若节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；若节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果
面试题59： 对称的二叉树
题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：利用递归进行判断，若左子树的左孩子等于右子树的右孩子且左子树的右孩子等于右子树的左孩子，并且左右子树节点的值相等，则是对称的。
面试题60： 把二叉树打印成多行
题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路：利用辅助空间链表或队列来存储节点，每层输出。
面试题61 ：按之字型顺序打印二叉树
题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，依此类推。
思路：利用两个栈的辅助空间分别存储奇数偶数层的节点，然后打印输出。或使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出。
面试题62： 序列化二叉树
题目：请实现两个函数，分别用来序列化和反序列化二叉树
思路：序列化：前序遍历二叉树存入字符串中；反序列化：根据前序遍历重建二叉树。
面试题63：二叉搜索树的第k个结点
题目：给定一颗二叉搜索树，请找出其中的第k大的结点
思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序，第k个结点就是第K大的节点，分别递归查找左右子树的第K个节点，或使用非递归借用栈的方式查找，当count=k时返回根节点。
面试题64： 数据流中的中位数
题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路：创建优先级队列维护大顶堆和小顶堆两个堆，并且小顶堆的值都大于大顶堆的值，2个堆个数的差值小于等于1，所以当插入个数为奇数时：大顶堆个数就比小顶堆多1，中位数就是大顶堆堆头；当插入个数为偶数时，使大顶堆个数跟小顶堆个数一样，中位数就是 2个堆堆头平均数。也可使用集合类的排序方法。
8.5 栈和队列
面试题65：滑动窗口的最大值
题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值
思路：两个for循环，第一个for循环滑动窗口，第二个for循环滑动窗口中的值，寻找最大值。还可以使用时间复杂度更低的双端队列求解。
8.6 回溯法
面试题66：矩阵中的路径
题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
思路：回溯法，双层for循环，判断每一个点，每次递归调用上下左右四个点，用flag标志是否已经匹配（return），进行判断点的位置是否越界，是否已经正确匹配，判断矩阵的路径与模式串的第index个字符是否匹配。
面试题67：机器人的运动范围
题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
思路：利用递归实现，每次只能走上下左右四个点，进行判断点的位置是否越界，点数之和是否大于K，是否已经走过了。
全剧终……
