本局部次要是 CavsZhouyou 在练习《剑指 Offer》时所做的笔记，次要波及算法相干常识和一些相干面试题时所做的笔记，分享这份总结给大家，帮忙大家对算法的能够来一次全方位的检漏和排查，感激原作者 CavsZhouyou 的付出，原文链接放在文章最下方，如果呈现谬误，心愿大家独特指出！

1. 二维数组中的查找

题目：在一个二维数组中，每一行都依照从左到右递增的程序排序，每一列都依照从上到下递增的程序排序。请实现一个函数，输出这样的
一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

（1）第一种形式是应用两层循环顺次遍历，判断是否含有该整数。这一种形式最坏状况下的工夫复杂度为 O(n^2)。

（2）第二种形式是利用递增序列的特点，咱们能够从二维数组的右上角开始遍历。如果以后数值比所求的数要小，则将地位向下挪动
，再进行判断。如果以后数值比所求的数要大，则将地位向左挪动，再进行判断。这一种形式最坏状况下的工夫复杂度为 O(n)。

2. 替换空格

题目：请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为 We Are Happy. 则通过替换之后的字符串为 We%20
Are%20Happy

思路：应用正则表达式，联合字符串的 replace 办法将空格替换为“%20”str.replace(/\s/g,"%20")

3. 从尾到头打印链表

题目：输出一个链表，从尾到头打印链表每个节点的值。思路：利用栈来实现，首先依据头结点以此遍历链表节点，将节点退出到栈中。当遍历实现后，再将栈中元素弹出并打印，以此来实现。栈的
实现能够利用 Array 的 push 和 pop 办法来模仿。

4. 重建二叉树

题目：输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。例如输
入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。思路：利用递归的思维来求解，首先先序序列中的第一个元素肯定是根元素。而后咱们去中序遍历中寻找到该元素的地位，找到后该元素的左
边局部就是根节点的左子树，左边局部就是根节点的右子树。因而咱们能够别离截取对应的局部进行子树的递归构建。应用这种形式的
工夫复杂度为 O(n)，空间复杂度为 O(logn)。

5. 用两个栈实现队列

题目：用两个栈来实现一个队列，实现队列的 Push 和 Pop 操作。思路：队列的一个根本特点是，元素先进先出。通过两个栈来模仿时，首先咱们将两个栈分为栈 1 和栈 2。当执行队列的 push 操作时，间接
将元素 push 进栈 1 中。当队列执行 pop 操作时，首先判断栈 2 是否为空，如果不为空则间接 pop 元素。如果栈 2 为空，则将栈 1 中
的所有元素 pop 而后 push 到栈 2 中，而后再执行栈 2 的 pop 操作。扩大：当应用两个长度不同的栈来模仿队列时，队列的最大长度为较短栈的长度的两倍。

6. 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的开端，咱们称之为数组的旋转。输出一个非递加排序的数组的一个旋转，输入旋转数组的
最小元素。例如数组 {3,4,5,1,2} 为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。NOTE：给出的所有元素都大于 0，若数组大
小为 0，请返回 0。思路：（1）咱们输出的是一个非递加排序的数组的一个旋转，因而原始数组的值递增或者有反复。旋转之后原始数组的值肯定和一个值相
邻，并且不满足递增关系。因而咱们就能够进行遍历，找到不满足递增关系的一对值，后一个值就是旋转数组的最小数字。（2）二分法

相干材料能够参考：
《旋转数组的最小数字》

7. 斐波那契数列

题目：大家都晓得斐波那契数列，当初要求输出一个整数 n，请你输入斐波那契数列的第 n 项。n<=39

思路：斐波那契数列的法则是，第一项为 0，第二项为 1，第三项当前的值都等于后面两项的和，因而咱们能够通过循环的形式，一直通过叠
加来实现第 n 项值的构建。通过循环而不是递归的形式来实现，工夫复杂度降为了 O(n)，空间复杂度为 O(1)。

8. 跳台阶

题目：一只青蛙一次能够跳上 1 级台阶，也能够跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。思路：跳台阶的问题是一个动静布局的问题，因为一次只可能跳 1 级或者 2 级，因而跳上 n 级台阶一共有两种计划，一种是从 n-1 跳上，一
种是从 n-2 级跳上，因而 f(n) = f(n-1) + f(n-2)。和斐波那契数列相似，不过初始两项的值变为了 1 和 2，前面每项的值等于后面两项的和。

9. 变态跳台阶

题目：

一只青蛙一次能够跳上 1 级台阶，也能够跳上 2 级……它也能够跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路：

变态跳台阶的问题同上一个问题的思考计划是一样的，咱们能够失去一个论断是，每一项的值都等于后面所有项的值的和。

f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 示意 2 阶一次跳 2 阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
…
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)

再次总结可得

        | 1 ,(n=0)
f(n) =  | 1 ,(n=1)
        | 2\*f(n-1),(n>=2)

10. 矩形笼罩

题目：咱们能够用 2*1 的小矩形横着或者竖着去笼罩更大的矩形。请问用 n 个 2*1 的小矩形无重叠地笼罩一个 2\*n 的大矩形，总共
有多少种办法？思路：仍旧是斐波那契数列的利用

11. 二进制中 1 的个数

题目：输出一个整数，输入该数二进制示意中 1 的个数。其中正数用补码示意。思路：一个不为 0 的整数的二进制示意，肯定会有一位为 1。咱们找到最左边的一位 1，当咱们将整数减去 1 时，最左边的一位 1 变为 0，它后
面的所有位都取反，因而将减一后的值与原值相与，咱们就会可能打消最左边的一位 1。因而判断一个二进制中 1 的个数，咱们能够判
断这个数能够经验多少次这样的过程。如：1100&1011=1000

12. 数值的整数次方

题目：给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。思路：首先咱们须要判断 exponent 正负和零取值三种状况，依据不同的状况通过递归来实现。

13. 调整数组程序使奇数位于偶数后面

题目：输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半
局部，并保障奇数和奇数，偶数和偶数之间的绝对地位不变。思路：因为须要思考到调整之后的稳定性，因而咱们能够应用辅助数组的形式。首先对数组中的元素进行遍历，每遇到一个奇数就将它退出到
奇数辅助数组中，每遇到一个偶数，就将它将入到偶数辅助数组中。最初再将两个数组合并。这一种办法的工夫复杂度为 O(n)，空间
复杂度为 O(n)。

14. 链表中倒数第 k 个节点

题目：输出一个链表，输入该链表中倒数第 k 个结点。思路：应用两个指针，先让第一个和第二个指针都指向头结点，而后再让第二个指针走 k-1 步，达到第 k 个节点。而后两个指针同时向后
挪动，当第二个指针达到开端时，第一个指针指向的就是倒数第 k 个节点了。

15. 反转链表

题目：输出一个链表，反转链表后，输入链表的所有元素。思路：通过设置三个变量 pre、current 和 next，别离用来保留前继节点、以后节点和后继结点。从第一个节点开始向后遍历，首先将当
前节点的后继节点保留到 next 中，而后将以后节点的后继节点设置为 pre，而后再将 pre 设置为以后节点，current 设置为 ne
xt 节点，实现下一次循环。

16. 合并两个排序的链表

题目：输出两个枯燥递增的链表，输入两个链表合成后的链表，当然咱们须要合成后的链表满足枯燥不减规定。思路：通过递归的形式，顺次将两个链表的元素递归进行比照。

17. 树的子结构

题目：输出两棵二叉树 A、B，判断 B 是不是 A 的子结构。（ps：咱们约定空树不是任意一个树的子结构）思路：通过递归的思维来解决

第一步首先从树 A 的根节点开始遍历，在左右子树中找到和树 B 根结点的值一样的结点 R。第二步两棵树同时从 R 节点和根节点以雷同的遍历形式进行遍历，顺次比拟对应的值是否雷同，当树 B 遍历完结时，完结比拟。

18. 二叉树的镜像

题目：操作给定的二叉树，将其变换为源二叉树的镜像。思路：从根节点开始遍历，首先通过长期变量保留左子树的援用，而后将根节点的左右子树的援用替换。而后再递归左右节点的子树替换。

19. 顺时针打印矩阵

题目：输出一个矩阵，依照从内向里以顺时针的程序顺次打印出每一个数字，例如，如果输出如下矩阵：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

思路：（1）依据左上角和右下角能够定位出一次要旋转打印的数据。一次旋转打印完结后，往对角别离后退和后退一个单位，能够确定下一
次须要打印的数据范畴。（2）应用模仿魔方逆时针解法，每打印一行，则将矩阵逆时针旋转 90 度，打印下一行，顺次反复。

20. 定义一个栈，实现 min 函数

题目：定义栈的数据结构，请在该类型中实现一个可能失去栈最小元素的 min 函数。思路：应用一个辅助栈，每次将数据压入数据栈时，就把以后栈外面最小的值压入辅助栈当中。这样辅助栈的栈顶数据始终是数据栈中最小
的值。

21. 栈的压入弹出

题目：输出两个整数序列，第一个序列示意栈的压入程序，请判断第二个序列是否为该栈的弹出程序。假如压入栈的所有数字均不相等。例如
序列 1,2,3,4,5 是某栈的压入程序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序
列的弹出序列。（留神：这两个序列的长度是相等的）思路：咱们能够应用一个辅助栈的形式来实现，首先遍历压栈程序，顺次将元素压入辅助栈中，每次压入元素后咱们首先判断该元素是否与出
栈程序中的此刻地位的元素相等，如果不相等，则将元素持续压栈，如果相等，则将辅助栈中的栈顶元素出栈，出栈后，将出栈程序中
的地位后移一位持续比拟。当压栈程序遍历实现后，如果辅助栈不为空，则阐明该出栈程序不正确。

22. 从上往下打印二叉树

题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。思路：实质上是二叉树的层序遍历，能够通过队列来实现。首先将根节点入队。而后对队列进行出队操作，每次出队时，将出队元素的左右子
节点顺次退出到队列中，直到队列长度变为 0 时，完结遍历。

23. 二叉搜寻树的后序遍历

题目：输出一个整数数组，判断该数组是不是某二叉搜寻树的后序遍历的后果。如果是则输入 Yes，否则输入 No。假如输出的数组的任意两
个数字都互不雷同。思路：对于一个非法而二叉树的后序遍历来说，最开端的元素为根元素。该元素后面的元素能够划分为两个局部，一部分为该元素的左子树，所有元素的值比根元素小，一部分为该元素的右子树，所有的元素的值比该根元素大。并且每一部分都是一个非法的后序序列，因而我
们能够利用这些特点来递归判断。

24. 二叉树中和为某一值门路

题目：输出一颗二叉树和一个整数，打印出二叉树中结点值的和为输出整数的所有门路。门路定义为从树的根结点开始往下始终到叶结点所经
过的结点造成一条门路。思路：通过对树进行深度优先遍历，遍历时保留以后节点的值并判断是否和期望值相等，如果遍历到叶节点不符合要求则回退解决。

25. 简单链表的复制

题目：输出一个简单链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个非凡指针指向任意一个节点），返回后果为
复制后简单链表的 head。（留神，输入后果中请不要返回参数中的节点援用，否则判题程序会间接返回空）思路：（1）第一种形式，首先对原有链表每个节点进行复制，通过 next 连接起来。而后当链表复制实现之后，再来设置每个节点的 ra
ndom 指针，这个时候每个节点的 random 的设置都须要从头结点开始遍历，因而工夫的复杂度为 O(n^2)。（2）第二种形式，首先对原有链表每个节点进行复制，并且应用 Map 以键值对的形式将原有节点和复制节点保留下来。当链表复
制实现之后，再来设置每个节点的 random 指针，这个时候咱们通过 Map 中的键值关系就能够获取到对应的复制节点，因而
不用再从头结点遍历，将工夫的复杂度升高为了 O(n)，然而空间复杂度变为了 O(n)。这是一种以空间换工夫的做法。（3）第三种形式，首先对原有链表的每个节点进行复制，并将复制后的节点退出到原有节点的前面。当链表复制实现之后，再进行
random 指针的设置，因为每个节点前面都跟着本人的复制节点，因而咱们能够很容易的获取到 random 指向对应的复制节点。最初再将链表拆散，通过这种办法咱们也可能将工夫复杂度升高为 O(n)。

26. 二叉搜寻树与双向链表

题目：输出一棵二叉搜寻树，将该二叉搜寻树转换成一个排序的双向链表。要求不能创立任何新的结点，只能调整树中结点指针的指向。思路：须要生成一个排序的双向列表，那么咱们应该通过中序遍历的形式来调整树结构，因为只有中序遍历，返回才是一个从小到大的排序
序列。根本的思路是咱们首先从根节点开始遍历，先将左子树调整为一个双向链表，并将左子树双向链表的开端元素的指针指向根节点，并
将根节点的左节点指向开端节点。再将右子树调整为一个双向链表，并将右子树双向链表的首部元素的指针指向根元素，再将根节点
的右节点指向首部节点。通过对左右子树递归调整，因而来实现排序的双向链表的构建。

27. 字符串的排列

题目：输出一个字符串，按字典序打印出该字符串中字符的所有排列。例如输出字符串 abc，则打印出由字符 a,b,c 所能排列进去的所有
字符串 abc,acb,bac,bca,cab 和 cba。输出形容：输出一个字符串，长度不超过 9（可能有字符反复），字符只包含大小写字母。思路：咱们能够把一个字符串看做是两个局部，第一部分为它的第一个字符，第二局部是它前面的所有字符。求整个字符串的一个全排列，可
以看做两步，第一步是求所有可能呈现在第一个地位的字符，即把第一个字符和前面的所有字符替换。第二步就是求前面所有字符的一
个全排列。因而通过这种形式，咱们能够以递归的思路来求出以后字符串的全排列。

详细资料能够参考：
《字符串的排列》

28. 数组中呈现次数超过一半的数字

题目：数组中有一个数字呈现的次数超过数组长度的一半。请找出这个数字。例如输出一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。因为数
字 2 在数组中呈现了 5 次，超过数组长度的一半，因而输入 2。如果不存在则输入 0。思路：（1）对数组进行排序，排序后的中位数就是所求数字。这种办法的工夫复杂度取决于咱们采纳的排序办法的工夫复杂度，因而最快为
O(nlogn)。（2）因为所求数字的数量超过了数组长度的一半，因而排序后的中位数就是所求数字。因而咱们能够将问题简化为求一个数组的中
位数问题。其实数组并不需要全排序，只须要局部排序。咱们通过利用快排中的 partition 函数来实现，咱们当初数组中随
机选取一个数字，而后通过 partition 函数返回该数字在数组中的索引 index，如果 index 刚好等于 n/2，则这个数字
便是数组的中位数，也即是要求的数，如果 index 大于 n/2，则中位数必定在 index 的右边，在右边持续寻找即可，反之
在左边寻找。这样能够只在 index 的一边寻找，而不必两边都排序，缩小了一半排序工夫，这种办法的工夫复杂度为 O(n)。（3）因为该数字的呈现次数比所有其余数字呈现次数的和还要多，因而能够思考在遍历数组时保留两个值：一个是数组中的一个数
字，一个是次数。当遍历到下一个数字时，如果下一个数字与之前保留的数字雷同，则次数加 1，如果不同，则次数减 1，如果
次数为 0，则须要保留下一个数字，并把次数设定为 1。因为咱们要找的数字呈现的次数比其余所有数字的呈现次数之和还要大，则要找的数字必定是最初一次把次数设为 1 时对应的数字。该办法的工夫复杂度为 O(n)，空间复杂度为 O(1)。

详细资料能够参考：
《呈现次数超过一半的数字》

29. 最小的 K 个数

题目：输出 n 个整数，找出其中最小的 K 个数。例如输出 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4。思路：（1）第一种思路是首先将数组排序，排序后再取最小的 k 个数。这一种办法的工夫复杂度取决于咱们抉择的排序算法的工夫简单
度，最好的状况下为 O(nlogn)。（2）第二种思路是因为咱们只须要取得最小的 k 个数，这 k 个数不肯定是按序排序的。因而咱们能够应用疾速排序中的 part
ition 函数来实现。每一次抉择一个枢纽值，将数组分为比枢纽值大和比枢纽值小的两个局部，判断枢纽值的地位，如果该枢
纽值的地位为 k-1 的话，那么枢纽值和它后面的所有数字就是最小的 k 个数。如果枢纽值的地位小于 k-1 的话，假如枢
纽值的地位为 n-1，那么咱们曾经找到了前 n 小的数字了，咱们就还须要到后半局部去寻找后半局部 k-n 小的值，进行划
分。当该枢纽值的地位比 k-1 大时，阐明最小的 k 个值还在左半局部，咱们须要持续对左半局部进行划分。这一种办法的平
均工夫复杂度为 O(n)。（3）第三种办法是保护一个容量为 k 的最大堆。对数组进行遍历时，如果堆的容量还没有达到 k，则间接将元素退出到堆中，这
就相当于咱们假如前 k 个数就是最小的 k 个数。对 k 当前的元素遍历时，咱们将该元素与堆的最大值进行比拟，如果比最
大值小，那么咱们则将最大值与其替换，而后调整堆。如果大于等于堆的最大值，则持续向后遍历，直到数组遍历实现。这一
种办法的均匀工夫复杂度为 O(nlogk)。

详细资料能够参考：
《寻找最小的 k 个数》

30. 间断子数组的最大和

题目：HZ 偶然会拿些业余问题来忽悠那些非计算机专业的同学。明天测试组开完会后，他又发话了: 在古老的一维模式识别中，经常须要计
算间断子向量的最大和, 当向量全为负数的时候，问题很好解决。然而，如果向量中蕴含正数，是否应该蕴含某个正数，并冀望旁边的
负数会补救它呢？例如：{6,-3,-2,7,-15,1,2,2}，间断子向量的最大和为 8（从第 0 个开始，到第 3 个为止）。你会不会被他忽悠
住？（子向量的长度至多是 1）思路：（1）第一种思路是间接暴力求解的形式，先以第一个数字为首往后开始叠加，叠加的过程中保留最大的值。而后再以第二个数字为首
往后开始叠加，并与先前保留的最大的值进行比拟。这一种办法的工夫复杂度为 O(n^2)。（2）第二种思路是，首先咱们察看一个最大和的间断数组的法则，咱们能够发现，子数组肯定是以负数结尾的，两头蕴含了正负数。因而咱们能够从第一个数开始向后叠加，每次保留最大的值。叠加的值如果为正数，则将叠加值初始化为 0，因为前面的数加上负
数只会更小，因而须要寻找下一个负数开始下一个子数组的判断。始终往后判断，直到这个数组遍历实现为止，失去最大的值。应用这一种办法的工夫复杂度为 O(n)。

详细资料能够参考：
《间断子数组的最大和》

31. 整数中 1 呈现的次数（待深刻了解）

题目：求出 1~13 的整数中 1 呈现的次数，并算出 100~1# 300 的整数中 1 呈现的次数？为此他特地数了一下 1~13 中蕴含 1 的数字有 1、10、11、12、13 因而共呈现 6 次，然而对于前面问题他就没辙了。ACMer 心愿你们帮帮他，并把问题更加普遍化，能够很快的求出任意非负整
数区间中 1 呈现的次数。思路：（1）第一种思路是间接遍历每个数，而后将判断每个数中 1 的个数，始终叠加。（2）第二种思路是求出 1 呈现在每位上的次数，而后进行叠加。

详细资料能够参考：
《从 1 到 n 整数中 1 呈现的次数：O(logn)算法》

32. 把数组排成最小的数

题目：输出一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输出数组{3，32，321}，则打印出这三个数字能排成的最小数字为 321323。思路：（1）求出数组的全排列，而后对每个排列后果进行比拟。（2）利用排序算法实现，然而比拟时，比拟的并不是两个元素的大小，而是两个元素正序拼接和逆序拼接的大小，如果逆序拼接的
后果更小，则替换两个元素的地位。排序完结后，数组的程序则为最小数的排列组合程序。

详细资料能够参考：
《把数组排成最小的数》

33. 丑数（待深刻了解）

题目：把只蕴含质因子 2、3 和 5 的数称作丑数。例如 6、8 都是丑数，但 14 不是，因为它蕴含因子 7。习惯上咱们把 1 当做是第一个丑数。求
按从小到大的程序的第 N 个丑数。思路：（1）判断一个数是否为丑数，能够判断该数一直除以 2，最初余数是否为 1。判断该数一直除以 3，最初余数是否为 1。判断一直除以
5，最初余数是否为 1。在不思考工夫复杂度的状况下，能够顺次遍历找到第 N 个丑数。（2）应用一个数组来保留已排序好的丑数，前面的丑数由后面生成。

34. 第一个只呈现一次的字符

题目：在一个字符串（1<= 字符串长度 <=10000，全副由大写字母组成）中找到第一个只呈现一次的字符，并返回它的地位。思路：（1）第一种思路是，从前往后遍历每一个字符。每遍历一个字符，则将字符与后边的所有字符顺次比拟，判断是否含有雷同字符。这
一种办法的工夫复杂度为 O(n^2)。（2）第二种思路是，首先对字符串进行一次遍历，将字符和字符呈现的次数以键值对的模式存储在 Map 构造中。而后第二次遍历时，去 Map 中获取对应字符呈现的次数，找到第一个只呈现一次的字符。这一种办法的工夫复杂度为 O(n)。

35. 数组中的逆序对

题目：在数组中的两个数字，如果后面一个数字大于前面的数字，则这两个数字组成一个逆序对。输出一个数组，求出这个数组中的逆序对
的总数 P。思路：（1）第一种思路是间接求解的形式，程序扫描整个数组。每扫描到一个数字的时候，一一比拟该数字和它前面的数字的大小。如果
前面的数字比它小，则这两个数字就组成了一个逆序对。假如数组中含有 n 个数字。因为每个数字都要和 O(n）个数字作比
较，因而这个算法的工夫复杂度是 O(n^2)。（2）第二种形式是应用归并排序的形式，通过利用归并排序合成后进行合并排序时，来进行逆序对的统计，这一种办法的工夫简单
度为 O(nlogn)。

详细资料能够参考：
《数组中的逆序对》

36. 两个链表的第一个公共结点

题目：输出两个链表，找出它们的第一个公共结点。思路：（1）第一种办法是在第一个链表上程序遍历每个结点，每遍历到一个结点的时候，在第二个链表上程序遍历每个结点。如果在第二
个链表上有一个结点和第一个链表上的结点一样，阐明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一
个链表的长度为 m，第二个链表的长度为 n。这一种办法的工夫复杂度是 O(mn）。（2）第二种形式是利用栈的形式，通过观察咱们能够发现两个链表的公共节点，都位于链表的尾部，以此咱们能够别离应用两个栈，顺次将链表元素入栈。而后在两个栈同时将元素出栈，比拟出栈的节点，最初一个雷同的节点就是咱们要找的公共节点。这
一种办法的工夫复杂度为 O(m+n)，空间复杂度为 O(m+n)。（3）第三种形式是，首先别离遍历两个链表，失去两个链表的长度。而后失去较长的链表与较短的链表长度的差值。咱们应用两个
指针来别离对两个链表进行遍历，首先将较长链表的指针挪动 n 步，n 为两个链表长度的差值，而后两个指针再同时挪动，判断所指向节点是否为同一节点。这一种办法的工夫复杂度为 O(m+n)，雷同对于上一种办法不须要额定的空间。

详细资料能够参考：
《两个链表的第一个公共结点》

37. 数字在排序数组中呈现的次数

题目：统计一个数字：在排序数组中呈现的次数。例如输出排序数组{ 1, 2, 3, 3, 3, 3, 4, 5}和数字 3，因为 3 在这个数组中出
现了 4 次，因而输入 4。思路：（1）第一种办法是间接对数组程序遍历的形式，通过这种办法来统计数字的呈现次数。这种办法的工夫复杂度为 O(n)。（2）第二种办法是应用二分查找的办法，因为数组是排序好的数组，因而雷同数字是排列在一起的。统计数字呈现的次数，咱们须要
去找到该段数字开始和完结的地位，以此来确定数字呈现的次数。因而咱们能够应用二分查找的形式来确定该数字的开始和完结
地位。如果咱们第一次咱们数组的两头值为 k，如果 k 值比所求值大的话，那么咱们下一次只须要判断后面一部分就行了，如
果 k 值比所求值小的话，那么咱们下一次就只须要判断前面一部分就行了。如果 k 值等于所求值的时候，咱们则须要判断该值
是否为开始地位或者完结地位。如果是开始地位，那么咱们下一次须要到后半局部去寻找完结地位。如果是完结地位，那么咱们
下一次须要到前半部分去寻找开始地位。如果既不是开始地位也不是完结地位，那么咱们就别离到前后两个局部去寻找开始和结
束地位。这一种办法的均匀工夫复杂度为 O(logn)。

38. 二叉树的深度

题目：输出一棵二叉树，求该树的深度。从根结点到叶结点顺次通过的结点（含根、叶结点）造成树的一条门路，最长门路的长度为树的深
度。思路：根节点的深度等于左右深度较大值加一，因而能够通过递归遍从来实现。

39. 均衡二叉树

题目：输出一棵二叉树，判断该二叉树是否是均衡二叉树。思路：（1）在遍历树的每个结点的时候，调用函数失去它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过 1，那么它
就是一棵均衡的二叉树。应用这种办法时，节点会被屡次遍历，因而会造成效率不高的问题。（2）在求一个节点的深度时，同时判断它是否均衡。如果不均衡则间接返回 -1，否则返回树高度。如果一个节点的一个子树的深
度为 -1，那么就间接向上返回 -1，该树曾经是不均衡的了。通过这种形式确保了节点只可能被拜访一遍。

40. 数组中只呈现一次的数字

题目：一个整型数组里除了两个数字之外，其余的数字都呈现了两次。请写程序找出这两个只呈现一次的数字。思路：（1）第一种形式是顺次遍历数组，记录下数字呈现的次数，从而找出两个只呈现一次的数字。（2）第二种形式，依据位运算的异或的性质，咱们能够晓得两个雷同的数字异或等于 0，一个数和 0 异或还是它自身。因为数组中
的其余数字都是成对呈现的，因而咱们能够将数组中的所有数顺次进行异或运算。如果只有一个数呈现一次的话，那么最初剩下
的就是落单的数字。如果是两个数只呈现了一次的话，那么最初剩下的就是这两个数异或的后果。这个后果中的 1 示意的是 A 和
B 不同的位。咱们取异或后果的第一个 1 所在的位数，如果是第 3 位，接着通过比拟第三位来将数组分为两组，雷同数字肯定会
被分到同一组。分组实现后再依照顺次异或的思路，求得残余数字即为两个只呈现一次的数字。

41. 和为 S 的间断负数序列

题目：小明很喜爱数学，有一天他在做数学作业时，要求计算出 9~16 的和，他马上就写出了正确答案是 100。然而他并不满足于此，他在想究
竟有多少种间断的负数序列的和为 100（至多包含两个数）。没多久，他就失去另一组间断负数和为 100 的序列：18,19,20,21,22。当初把问题交给你，你能不能也很快的找出所有和为 S 的间断负数序列？Good Luck! 输入形容：输入所有和为 S 的间断负数序列。序
列内依照从小至大的程序，序列间依照开始数字从小到大的程序。思路：保护一个负数序列数组，数组中初始只含有值 1 和 2，而后从 3 顺次往后遍历，每遍历到一个元素则将这个元素退出到序列数组中，而后
判断此时序列数组的和。如果序列数组的和大于所求值，则将第一个元素（最小的元素弹出）。如果序列数组的和小于所求值，则持续
往后遍历，将元素退出到序列中持续判断。当序列数组的和等于所求值时，打印出此时的负数序列，而后持续往后遍历，寻找下一个连
续序列，直到数组遍历实现终止。

详细资料能够参考：
《和为 s 的间断负数序列》

42. 和为 S 的两个数字

题目：输出一个递增排序的数组和一个数字 S，在数组中查找两个数，是的他们的和正好是 S，如果有多对数字的和等于 S，输入两个数
的乘积最小的。输入形容：对应每个测试案例，输入两个数，小的先输入。思路：首先咱们通过法则能够发现，和雷同的两个数字，两个数字的差值越大，乘积越小。因而咱们只须要从数组的首尾开始找到第一对和
为 s 的数字对进行了。因而咱们能够应用双指针的形式，左指针初始指向数组的第一个元素，右指针初始指向数组的最初一个元素。而后首先判断两个指针指向的数字的和是否为 s，如果为 s，两个指针指向的数字就是咱们须要寻找的数字对。如果两数的和
比 s 小，则将左指针向左挪动一位后持续判断。如果两数的和比 s 大，则将右指针向右挪动一位后持续判断。

详细资料能够参考：
《和为 S 的字符串》

43. 左旋转字符串

题目：汇编语言中有一种移位指令叫做循环左移（ROL），当初有个简略的工作，就是用字符串模仿这个指令的运算后果。对于一个给定的
字符序列 S，请你把其循环左移 K 位后的序列输入。例如，字符序列 S=”abcXYZdef”，要求输入循环左移 3 位后的后果，即“X
YZdefabc”。是不是很简略？OK，搞定它！思路：字符串裁剪后拼接

44. 翻转单词程序列

题目：牛客最近来了一个新员工 Fish，每天晚上总是会拿着一本英文杂志，写些句子在本子上。共事 Cat 对 Fish 写的内容颇感兴趣，有
一天他向 Fish 借来翻看，但却读不懂它的意思。例如，“student. a am I”。起初才意识到，这家伙原来把句子单词的程序翻转了，正确的句子应该是“I am a student.”。Cat 对一一的翻转这些单词程序可不在行，你能帮忙他么？思路：通过空格将单词分隔，而后将数组反序后，从新拼接为字符串。

45. 扑克牌的顺子

题目：LL 明天情绪特地好，因为他去买了一副扑克牌，发现外面竟然有 2 个大王，2 个小王（一副牌本来是 54 张 ^\_^）... 他随机从中抽出
了 5 张牌，想测测本人的手气，看看能不能抽到顺子，如果抽到的话，他决定去买体育彩票，嘿嘿！！“红心 A，黑桃 3，小王，大王，方片 5”，“Oh My God!”不是顺子..... LL 不快乐了，他想了想，决定大 \ 小王能够看成任何数字，并且 A 看作 1，J 为 11，Q 为 12，K 为 13。下面的 5 张牌就能够变成“1,2,3,4,5”（大小王别离看作 2 和 4），“So Lucky!”。LL 决定去买体育彩票啦。当初，要求你应用这幅牌模仿下面的过程，而后通知咱们 LL 的运气如何。为了不便起见，你能够认为大小王是 0。思路：首先判断 5 个数字是不是间断的，最直观的办法是把数组排序。值得注意的是，因为 0 能够当成任意数字，咱们能够用 0 去补满数
组中的空缺。如果排序之后的数组不是间断的，即相邻的两个数字相隔若干个数字，但只有咱们有足够的。能够补满这两个数字的空
缺，这个数组实际上还是间断的。于是咱们须要做 3 件事件：首先把数组排序，再统计数组中 0 的个数，最初统计排序之后的数组中相邻数字之间的空缺总数。如
果空缺的总数小于或者等于 0 的个数，那么这个数组就是间断的：反之则不间断。最初，咱们还须要留神一点：如果数组中的非 0
数字反复呈现，则该数组不是间断的。换成扑克牌的形容形式就是如果一副牌里含有对子，则不可能是顺子。

详细资料能够参考：
《扑克牌的顺子》

46. 圆圈中最初剩下的数字（约瑟夫环问题）

题目：0, 1, … , n-1 这 n 个数字排成一个圈圈，从数字 0 开始每次从圆圏里删除第 m 个数字。求出这个圈圈里剩下的最初一个数
字。思路：（1）应用环形链表进行模仿。（2）依据法则得出（待深刻了解）

详细资料能够参考：
《圆圈中最初剩下的数字》

47. 1+2+3+…+n

题目：求 1+2+3+...+n，要求不能应用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。思路：因为不能应用循环语句，因而咱们能够通过递归来实现。并且因为不可能应用条件判断运算符，咱们能够利用 && 操作符的短路特
性来实现。

48. 不必加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得应用 +、-、×、÷ 四则运算符号。思路：通过位运算，递归来实现。

49. 把字符串转换成整数。

题目：将一个字符串转换成一个整数，要求不能应用字符串转换整数的库函数。数值为 0 或者字符串不是一个非法的数值则返回 0。输出描
述：输出一个字符串，包含数字字母符号，能够为空。输入形容：如果是非法的数值表白则返回该数字，否则返回 0。思路：首先须要进行符号判断，其次咱们依据字符串的每位通过减 0 运算转换为整数和，顺次依据位数叠加。

50. 数组中反复的数字

题目：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不知
道每个数字反复了几次。请找出数组中任意一个反复的数字。思路：（1）首先将数组排序，排序后再进行判断。这一种办法的工夫复杂度为 O(nlogn)。（2）应用 Map 构造的形式，顺次记录下每一个数字呈现的次数，从而能够判断是否呈现反复数字。这一种办法的工夫复杂度为 O
(n)，空间复杂度为 O(n)。（3）从数组首部开始遍历，每遍历一个数字，则将该数字和它的下标相比拟，如果数字和下标不等，则将该数字和它对应下标的值
替换。如果对应的下标值上曾经是正确的值了，那么阐明以后元素是一个反复数字。这一种办法绝对于上一种办法来说不须要
额定的内存空间。

51. 构建乘积数组

题目：给定一个数组 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]。不能应用除法。思路：（1）C[i]=A[0]×A[1]×...×A[i-1]=C[i-1]×A[i-1]
      D[i]=A[i+1]×...×A[n-1]=D[i+1]×A[i+1]
      B[i]=C[i]×D[i]
       将乘积分为前后两个局部，别离循环求出后，再进行相乘。（2）下面的办法须要额定的内存空间，咱们能够引入两头变量的形式，来升高空间复杂度。（待深刻了解）

详细资料能够参考：
《构建乘积数组》

52. 正则表达式的匹配

题目：请实现一个函数用来匹配包含 '.' 和 '_' 的正则表达式。模式中的字符 '.' 示意任意一个字符，而 '_' 示意它后面的字符能够呈现任
意次（蕴含 0 次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，然而与 "aa.a" 和 "ab\*a" 均不匹配。思路：（1）状态机思路（待深刻了解）

详细资料能够参考：
《正则表达式匹配》

53. 示意数值的字符串

题目：请实现一个函数用来判断字符串是否示意数值（包含整数和小数）。例如，字符串 "+100","5e2","-123","3.1416" 和 "-1E-
16"都示意数值。然而"12e","1a3.14","1.2.3","+-5"和"12e+4.3" 都不是。、思路：利用正则表达式实现

54. 字符流中第一个不反复的字符

题目：请实现一个函数用来找出字符流中第一个只呈现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只呈现一次
的字符是 "g"。当从该字符流中读出前六个字符 "google" 时，第一个只呈现一次的字符是 "l"。输入形容：如果以后字符流
没有存在呈现一次的字符，返回 #字符。思路：同第 34 题

55. 链表中环的入口结点

题目：一个链表中蕴含环，如何找出环的入口结点？思路：首先应用快慢指针的形式咱们能够判断链表中是否存在环，当快慢指针相遇时，阐明链表中存在环。相遇点肯定存在于环中，因而我
们能够从应用一个指针从这个点开始向前挪动，每挪动一个点，环的长度加一，当指针再次回到这个点的时候，指针走了一圈，因而
通过这个办法咱们能够失去链表中的环的长度，咱们将它记为 n。而后咱们设置两个指针，首先别离指向头结点，而后将一个指针先挪动 n 步，而后两个指针再同时挪动，当两个指针相遇时，相遇
点就是环的入口节点。

详细资料能够参考：
《链表中环的入口结点》
《《剑指 offer》——链表中环的入口结点》

56. 删除链表中反复的结点

题目：在一个排序的链表中，存在反复的结点，请删除该链表中反复的结点，反复的结点不保留，返回链表头指针。例如，链表 1->2->3-

> 3->4->4->5 解决后为 1->2->5

思路：解决这个问题的第一步是确定删除的参数。当然这个函数须要输出待删除链表的头结点。头结点可能与前面的结点反复，也就是说头
结点也可能被删除，所以在链表头额定增加一个结点。接下来咱们从头遍历整个链表。如果以后结点的值与下一个结点的值雷同，那么它们就是反复的结点，都能够被删除。为了保障删除
之后的链表依然是相连的而没有两头断开，咱们要把以后的前一个结点和前面值比以后结点的值要大的结点相连。咱们要确保 prev
要始终与下一个没有反复的结点连贯在一起。

57. 二叉树的下一个结点

题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历程序的下一个结点？树中的结点除了有两个别离指向左右子结点的指针以外，还有一个指向父节点的指针。思路：这个问题咱们能够分为三种状况来探讨。第一种状况，以后节点含有右子树，这种状况下，中序遍历的下一个节点为该节点右子树的最左子节点。因而咱们只有从右子节点
登程，始终沿着左子节点的指针，就能找到下一个节点。第二种状况是，以后节点不含有右子树，并且以后节点为父节点的左子节点，这种状况下中序遍历的下一个节点为以后节点的父节
点。第三种状况是，以后节点不含有右子树，并且以后节点为父节点的右子节点，这种状况下咱们沿着父节点始终向上查找，直到找到
一个节点，该节点为父节点的左子节点。这个左子节点的父节点就是中序遍历的下一个节点。

58. 对称二叉树

题目：请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。思路：咱们对一颗二叉树进行前序遍历的时候，是先拜访左子节点，而后再拜访右子节点。因而咱们能够定义一种对称的前序遍历的形式，就是先拜访右子节点，而后再拜访左子节点。通过比拟两种遍历形式最初的后果是否雷同，以此来判断该二叉树是否为对称二叉
树。

59. 按之字形程序打印二叉树（待深刻了解）

题目：请实现一个函数依照之字形程序打印二叉树，即第一行依照从左到右的程序打印，第二层依照从右到左的程序打印，即第一行依照
从左到右的程序打印，第二层依照从右到左程序打印，第三行再依照从左到右的程序打印，其余以此类推。思路：按之字形程序打印二叉树须要两个栈。咱们在打印某一行结点时，把下一层的子结点保留到相应的栈里。如果以后打印的是奇数层，则先保留左子结点再保留右子结点到一个栈里；如果以后打印的是偶数层，则先保留右子结点再保留左子结点到第二个栈里。每
一个栈遍历实现后进入下一层循环。

详细资料能够参考：
《按之字形程序打印二叉树》

60. 从上到下按层打印二叉树，同一层结点从左至右输入。每一层输入一行。

题目：从上到下按层打印二叉树，同一层的结点按从左到右的程序打印，每一层打印一行。思路：用一个队列来保留将要打印的结点。为了把二叉树的每一行独自打印到一行里，咱们须要两个变量：一个变量示意在以后的层中还
没有打印的结点数，另一个变量示意下一次结点的数目。

61. 序列化二叉树（带深刻了解）

题目：请实现两个函数，别离用来序列化和反序列化二叉树。思路：数组模仿

62. 二叉搜寻树的第 K 个节点

题目：给定一颗二叉搜寻树，请找出其中的第 k 小的结点。思路：对一颗树首先进行中序遍历，在遍历的同时记录曾经遍历的节点数，当遍历到第 k 个节点时，这个节点即为第 k 大的节点。

63. 数据流中的中位数（待深刻了解）

题目：如何失去一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有值排序之后位于两头的数值。如果数据
流中读出偶数个数值，那么中位数就是所有数值排序之后两头两个数的平均值。

64. 滑动窗口中的最大值（待深刻了解）

题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输出数组 {2,3,4,2,6,2,5,1} 及滑动窗口的
大小 3，那么一共存在 6 个滑动窗口，他们的最大值别离为 {4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1} 的滑动窗口有以下
6 个：{[2,3,4],2,6,2,5,1}，{2,[3,4,2],6,2,5,1}，{2,3,[4,2,6],2,5,1}，{2,3,4,[2,6,2],5,1}，{2
,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。思路：应用队列的形式模仿

65. 矩阵中的门路（待深刻了解）

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条蕴含某字符串所有字符的门路。门路能够从矩阵中的任意一个格子开始，每
一步能够在矩阵中向左，向右，向上，向下挪动一个格子。如果一条门路通过了矩阵中的某一个格子，则该门路不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中蕴含一条字符串 "bcced" 的门路，然而矩阵中不蕴含 "abcb" 门路，因为字符串的
第一个字符 b 占据了矩阵中的第一行第二个格子之后，门路不能再次进入该格子。

66. 机器人的静止范畴（待深刻了解）

题目：地上有一个 m 行和 n 列的方格。一个机器人从坐标 0,0 的格子开始挪动，每一次只能向左，右，上，下四个方向挪动一格，然而不能
进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人可能进入方格（35,37），因为 3+5+3+7 = 18。然而，它不能进入方格（35,38），因为 3+5+3+8 = 19。请问该机器人可能达到多少个格子？

剑指 offer 相干材料能够参考：

• 《剑指 offer 题目练习及思路剖析》
• 《JS 版剑指 offer》
• 《剑指 Offer 学习心得》

举荐

笔者再次墙裂举荐珍藏这篇原文，收录于 CavsZhouyou – 🐜 前端面试温习笔记，这个仓库是原作者校招时的前端温习笔记，次要总结一些比拟重要的知识点和前端面试问题，心愿对大家有所帮忙。

最初如果文章和笔记能带您一丝帮忙或者启发，请不要悭吝你的赞和珍藏，你的必定是我后退的最大能源 😁

附笔记链接，浏览往期更多优质文章可移步查看，喜爱的能够给我点赞激励哦：https://github.com/Wscats/art…