剑指offer题解

总结分析了剑指offer中每道题的解题思路

剑指offer题解

65题滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值

使用双向队列记录窗口中最大值的序号。窗口开始滑动时，也就是双向队列准备从尾部压入数字时，先判断队列头部的序号如果超出窗口范围，则弹出队列（每次只判断一个即可），队列的尾部所有小于当前要压入值的序号全部弹出，最后压入当前值。队列的头部即为当前窗口最大值的序号。

64题数据流之中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

使用一个大顶堆记录前一半的数据，一个小顶堆记录后一半的数据。如果加入的数是奇数，应该最后会加入到大顶堆中，所以要先加入到小顶堆中，再吧小顶堆的堆顶加入到大顶堆，偶数的情况同理。

63题二叉搜索树的第K个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。

中序遍历即为顺序遍历。

62题序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。这里没有规定序列化的方式

选择遍历方式（前序易理解），并定义好空结点的字符和分割字符即可。

61题之字形打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

同层次遍历，在反向的层次倒序即可。

60题把二叉树打印成多行

层次遍历

通过队列实现层次遍历，每次从队列去一个结点，并把其孩子压入队列。每层遍历前记录下该层的结点数（当前队列的结点数），即可分成多行。

59题对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

左右子树开始遍历比较，左子树的左孩子与右子树的右孩子进行比较（另一个孩子相同），收敛条件是同时为空为真，不同时为空或者值不相等为假。

58题二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。

中序遍历为左根右，所以下一个结点的情况为：

如果有右孩子，则为右孩子的最左结点
如果没有右孩子，则为第一个右向父结点（孩子是左结点）

57题删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

先头插一个dummy结点，之后每次判断下一个结点和下下一个结点是否相等，如果相等一直循环找到不相等的结点接到当前结点之后。

56题链表中环的入口结点

一个链表中包含环，请找出该链表的环的入口结点。

快慢指针，到相交的地方距入口与起始点到入口的距离相等，之后就可以从起始位置同时走，这次相交的位置即为入口结点。

2 * (x + y) = x + 2 * y + z 可以得出x = z

55题字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

一个linkedHashset保存当前一次的字符，hashset保存已经重复的字符。当字符流入的时候先判断hashset有没有，如果hashset没有，linkedHashset有，则说明当前字符第一次重复，从linked中删去加入hashset。

54题表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

注意起始的正负号，可能有小数点，小数点和整数后面可能会有e。 new String(str).matches(“[+-]?\d*(\.\d+)?([eE][+-]?\d+)?”);

53题正则表达式匹配

请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。

使用动态规划的方法。dp[i][j] 表示s[0…i]和p[0…j]是否匹配，状态转移方程为：

p[j-1]=’*’ ：dp[0][j]=dp[0][j-2]
s[i-1]== p[j-1] || p[j-1] ==’.’：dp[i][j]=dp[i-1][j-1]

p[j-1]=’*’ ：

p[j-2]== s[i-1]

p[j-2]==’.’：dp[i][j] = dp[i][j-1]

dp[i][j-2]

dp[i-1][j]（匹配一个，多个或；零个）

其他：dp[i][j] = dp[i][j-2] 只能匹配零个

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]。不能使用除法。

B[i]通过两次迭代得到，第一次B[0]=1,B[1]=B[0]A[0],B[2]=B[1]A[1]。这样B就是呈阶梯状的，包含了乘积数组的前半部分，同理第二次得到后半部分的阶梯状，都正好少一个A[i]

51题数组中的重复数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

排序查重
hashmap查重
把数字交换到自己的位置（序号）：如果数字已经在自己的位置则继续迭代下一个，如果不在则交换到自己的位置，如果发现要交换的位置上已经有正确的数字则是重复数字。

49题把字符串转换成整数

首先判断正负，再略去开头的符号和0，之后每读一位，就把之前的数乘10再加上当前位。

47题不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

用位运算模拟加法。

异或表示没有进位的加法，而进位的产生是有1 + 1= 10造成的，正好与操作可以得到进位的情况。 a ^ b表示没有进位的加法结果，（a & b） « 1表示所有的进位，可以递归的把a ^ b和（a & b） « 1，直到没有进位。可以收敛的原因是（a & b） « 1右边会不断的多0，直到最后全是0。

46题求1+2+3+…+n

要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

通过递归得到。可以通过boolean b = a && b 达到短路b的效果，java中不能只写后半部分，boolean b一定要有。

public int Sum_Solution(int n) {
    int sum = n;
    boolean b = (n != 0) && (sum += Sum_Solution(n - 1)) > 0;
    return sum;
}

45题圆圈中最后剩下的数

约瑟夫环

圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。

44题扑克牌顺序

扑克牌有两个大王，两个小王，可以当做任何牌，抽五张牌判断是不是顺子。

排序后看0能不能补后面差的空缺，存在相等的也不是顺子

43题反转单词顺序列

“student题a am I”反转为“I am a student.”

先翻转所有字符，再逐个翻转每个单词。
用栈先入后出实现翻转。

42题左旋转字符串

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。

与翻转单词顺序类似，先全部翻转，再单独翻转每一部分。
S后几位+S的前K位

41题和为S的连续正数序列

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

类似于滑动窗口的概念，和小于S则窗口向右扩展，和大于S则窗口左侧收缩一个。

40题数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。

利用了a ^ a = 0过滤掉所有出现两次的数。而其他两个数必定存在一位不相同，可以借助这一位把数组分为两部分，正好把这两个数分开，再连续异或就可以分别得到这两个数了。得到最右侧不为0的位的方法为diff &= -diff。由于是以补码的形式存储，所以与负数取与就只有一位为1，正好是最右侧为1的位置。

39题平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

左子树和右子树深度的差距不超过1。

39题二叉树的深度

输入一棵二叉树，求该树的深度。

递归求左右子树的深度，取其中较大值并加1即为树的深度。

38题数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

通过二分查找找到该数字，从分别从前向和后向遍历确定次数

37题两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

链表必定为Y型，先确定两个链表长度，长链表先走差值，再同步走。

36题数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数

通过归并排序的交换次数记录逆序对。

35题第一个只出现一次的字符位置

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。

计数法，记录下每个字符的次数，再遍历找到第一个只出现一次的字符。

34题丑数

把只包含因子2、3和5的数称作丑数（Ugly Number）。输出第n个丑数。

dp为丑数序列,dp[0]=1 每个新的丑数一定是老的丑数乘2,3或5得到，所以可以记录下当前还没有由乘2，3，5得到新的丑数序号i2,i3,i5 新的丑数为min（dp[i2] * 2, dp[i3] * 3, dp[i5] * 5），得到新的丑数后更新序号（自增）

33题把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

按照拼接之后的字典序排序，也就是定义s1+s2 > s2+s1时，表示s1>s2，之后再从小到大拼接起来。

32题从1到n整数中1出现的次数

public int NumberOf1Between1AndN_Solution(int n) {
    int cnt = 0;
    for (int m = 1; m <= n; m *= 10) {
        int a = n / m, b = n % m;
        cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
    }
    return cnt;
}

31题连续子数组的最大和

{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为8(从第0个开始,到第3个为止)

贪心思想：按顺序进行累加，并记录最大值，当和为负数时放弃之前的累加，从0重新开始。

30题最小的K个数

输入n个整数，找出其中最小的K个数。

快排中partition
大顶堆

29题数组中出现次数超过一半的数字

排序后再统计个数时间复杂度过高。可以使用最大投票算法，使用count记录一个元素出现的次数，当遍历的元素与该元素相等，则count++，否则count–。如果count==0，则说明当前遍历的前i个元素没有majority，或者没有超过i/2。重新记录元素，继续上述过程，在剩下的部分中最多的元素仍然是占大多数的，所以仍然可以找到。

28题字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列

全排列的问题，可以使用回溯法，但是存在相同的字母的问题。通过boolean数组记录每个位有没有使用，并通过i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]确保相同的字母只有一种排列

27题二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

二叉搜索树的中序遍历就是按顺序的，在遍历的过程中通过变量pre保存前一个结点，遍历的时候连接pre即可。

26题复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。复制这个链表。

在每个结点后面插入复制的结点，在复制随机链接，最后拆分。也就是cur.next = cur.next.next。

25题二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.

回溯法，把当前结点加入到path后，从target中减去val，收敛条件是target是0，并且是叶子节点。

24题二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

后序遍历最后一个是根节点，可以把之前的节点分为两部分，前部分都比自己小，后部分都比自己大。每一部分也递归地符合这个规律，当有不符的时候就说明不是。

23题从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

用队列层次遍历

22题栈的压入弹出序列

输入两个整数序列（均不相等），第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

用一个栈做模拟，按照压入顺序进行压入，压入的时候判断当前栈顶是否与弹出的第一个数字相等，相等就弹出，以此类推，看最后弹出序列是不是为空。

21题包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

使用两个栈，其中一个栈正常的压入值，另一个栈压入当前栈顶和要压入值中的较小值，最小栈的栈顶即为当前最小值。这样只有正常的栈中弹出最小的值时，最小栈中才会弹出这个值。

20题顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字

{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };表示转向方向。

19题二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

交换左右子树，并递归地左右子树也做镜像操作。

18题树的子结构

输入两颗二叉树A，B，判断B是不是A的子结构。

先从A中找到与B跟结点相同的结点，再判断子树是否与B有相同结构，要注意遍历判断相同结构的时候不能通过A和B不同时为null就判断不是，A可能还会有结点。

17题合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表

每次找两个链表中较小的加入到新的结点，最后还不为空的链表接到新的链表之后。

16题反转链表

输入一个链表，反转链表后，输出链表的所有元素

三指针：分别保存下一个结点，当前结点和前一个结点。遍历的时候next=cur.next; cur.next=pre; pre = cur; cur = next;
头插法：遍历原链表，插入到新链表的头部

15题链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

双指针，一个指针先走k步，再同时走，最后慢指针即为倒数第k个结点。

14题调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

通过一个辅助数组。先遍历一次得到奇数的数量，确定第一个偶数的序号，再遍历一次，奇数按顺序放在前半部分，偶数放在后半部分即可。

12题打印1到最大的N位数

给定一个数字N，打印从1到最大的N位数。

直接通过pow（10，N）可能会超过INT_MAX。用char数组，回溯法得到所有数。

11题数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

考虑负数。可以把整数次方x分治为x/2，也就是pow（base * base，x/2），这样可以把O（n）降低为O（logn）

10题二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

不断的n & (n-1)，每次这个操作最右边的1都会变为0，n为0迭代的次数即为1的个数。

9题斐波那契数列

现在要求输入一个整数n，请你输出斐波那契数列的第n项

动态规划，记录之前已经计算过的子问题：f(n)=f(n-1)+f(n-2)

跳台阶，矩形覆盖都是类似的题。

8题旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减序列的一个旋转，输出旋转数组的最小元素。

依然是二分查找的思想，注意二分查找中判断的等号以及序号的取值：

如果a[l]=a[m]=a[h]，说明l-h包含旋转点，无法判断是在哪半部分，从l遍历到h，第一个变小的即是最小的
如果a[m]<=a[h]，h=m
否则l=m+1

7题用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

push动作就正常的向第一个栈push，pop动作从第二个栈pop，如果第二个栈为空则把第一个栈的数倒入第二个栈

6题重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

通过后序遍历确定根，通过根把中序遍历分为两个子树，递归这个过程

5题从尾到头打印链表

输入一个链表，从尾到头打印链表每个节点的值。

利用栈先入后出的特性倒序输出
通过递归倒序输出

4题替换空格

请实现一个函数，将一个字符串中的空格替换成“%20”

为了减少移动的次数，先遍历一遍得到空格数量，确定替换后字符串的长度，从后往前替换。

3题二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从右上角的元素出发，遍历最后一列，如果小于查找的数就继续向下遍历，如果大于查找的数就向左遍历查找。时间复杂度O（m+n）