前言
为了避免每次在牛客IDE上做题的紧张，我决定重新刷几遍《剑指offer》，记录下每次遇到的坑点。
03 重复数字
一看就知道需要调换数组中的元素使它应该到指定的位置。
这里的坑点是当进行交换的时候，不能简单进行交换，因为会进行修改，所以切记需要保存下来才可以修改。
04 二维数组查找
从右上角开始判断的题目，注意二维数组如果是空的判断。
05 替换空格
对于java来说不是问题。
06 从尾到头打印单项链表
两种思路，一种是通过利用额外的空间存储，另外一种是通过递归的方法。
如果你想通过反转链表来做，需要和面试官交流，因为一般不让修改原始数据。
第一种通过额外的存储空间，我的习惯使用deque，记得不要一边遍历，一边删除。
第二种是递归。
07 重建二叉树
递归没问题。递归的跳出的条件是start>end，我一开始写了start>=end，这样会漏掉几个数字。
然后记得搞清楚加一减一即可。
08 二叉树中序遍历的下一个
如果一个节点有右节点，那么就是右节点下的最左的那个节点。
如果一个节点它没有右节点，同时它又是左节点，那么就应该遍历父节点。
如果一个节点它没有右节点，同时它也不是左节点，那么就继续往上找，直到找到根节点。
09 两个栈来完成队列
一个栈只负责用来Push，另外一个栈只负责用来pop，一旦另外一个栈没东西了，就从第一个栈中倒过去。
那如何用两个队列来实现栈呢？只需要把n-1个元素出队列放到另外一个队列中，然后把队列中剩余的那个弹出即可。
10 斐波那契数列
比较简单就跳过了。
11 找出旋转数组中最小的数字
这题比较难。首先需要和最右边right进行比较，如果两者相等，那么则是right=mid，而不是right = mid-1
12 矩阵中的路径
DFS，注意是进去的时候需要判断，目标位置的数值和当前的index是否相等。
13 机器人的运动范围
感觉没什么意思，这题我就跳过了。
14 剪绳子
就是简单的取3出来。
15 二进制中1的个数
只需要n&(n-1)，就可以消去其中最后的一个1。当然也可以用>>>来进行右移。
扩展：如果把一个二进制通过转变01来变成另外一个二进制，可以让两者进行异或^然后来计算
16 数值的整数次方
这道题有几个坑，首先要考虑幂次的正负，不能简单的把负数直接改成正的，因为最低的负数是不能直接变正数的。其次是记得把中间的结果记下来。
17 打印从1-n个9的的所有数字
看一眼，就知道是DFS做的。注意考虑大数的问题。
18 删除链表节点
？？？那手动写一个链表吧
扩展：如何删除链表中的重复节点。注意头部的问题。
19 正则表达式匹配
我觉得难度太大了，面试官是不会问的。
20 表示数值的字符串
….意义不明
21 使所有奇数位于偶数前面
如果只是要求这样，可以直接用双指针完成。
但是如果是要求算法的稳定性，那么必然是需要花费O(n2)的时间，或者拿O(n)的空间来作为代价的。
思路是这样的，每一轮，我都把一个偶数通过交换的方式给换到最后面，然后下一轮就减一来减少总遍历个数来完成。非常类似冒泡。
22 删除倒数第K个节点
利用快慢指针来做，需要注意和面试官讨论K的范围。
23 链表中环的入口
这道题首先应该跟面试官交流是否确保链表中有环，如果有的话再去找环。
总结：对于链表的
24 反转链表
常考常考！！一定要记得非常熟练！
还需要掌握递归的方法。但是递归真的是恶心了。
25 合并两个有序链表
我之前写的代码比较恶心，所以需要掌握以下简介的写法。而且这里我写的时候想的是新创建一个节点，然后复制，这里相当于浪费了非常多的空间，其实只需要对原来的链表进行修改就可以了。
而且同时需要掌握递归和非递归两种写法。
扩展：掌握K个有序链表的排序，利用的是小顶堆。
26 树的子结构
终于到树了。树的题目十有八九肯定是递归。这里我第一次写的时候有问题，其实是需要两个递归，但是我只用了一个。
27 二叉树的镜像
交换左右子树，并且对左右子树进行相同的操作即可。还可以使用非递归的方法，就是利用BFS进行遍历，然后对于每个出栈的元素，交换它的左右子树即可。
28 判断二叉树是否对称
这个题真的是做一次不会，做一次不会。
首先你需要自己实现一个函数来判断两个节点是否是对称的，然后需要判断
29 矩阵打印
我自己做的方法是统计出一共有多少个节点要打印，这样能够防止多打印造成的越界等问题的发生。不过这种题目其实非常不适合在面试的时候考查。
30 最小栈
利用一个辅助栈来完成的。这里需要注意的是，当辅助栈是空的时候，就直接把当前的元素放进去，这是我踩过的坑。
31 栈的出栈入栈顺序
照着自己的思路来，就是简单的模拟。
32 BFS打印二叉树
用一个队列就可以了。毫无难度。
记得最后一层是全部是null的层，所以需要判断一下再入。或者是直接不把null给加到队列中去也行。
如果是之字形打印的话，可以通过reverse做一下。
33 二叉搜索树的后序遍历
第一种方法，递归。第一次写的太复杂了。可以从头开始遍历，然后找到第一个比end大的数字，这个数字是右边子树的开始，然后接着开始往下找，看能不能找到第一个比它小的数字，如果能找到则必然不是。
第二种方法，单调栈，单调栈比较难，但是还是要掌握的。
34 二叉树中和为某个值
我自己做的是利用递归，看别人做的是利用的前序遍历做的。
其实用DFS做的思路是最清晰最好的。
35 复杂链表的复制
emmmm 就是每个节点之后复制一下，然后就能找到random之后的节点了。
36 二叉搜索树和双向链表
把二叉搜索树变成一个双向链表。字节二面问的问题，我当时没写出来，而且写的巨复杂。
37 序列化二叉树
可以利用BFS进行遍历，这样就是一个满二叉树。然后满二叉树可以直接用
38 字符串的排列
很简单的DFS，但是要求的是不能重复的，所以需要注意。不能重复的话，只需要确保之后没有被访问即可。
扩展：不是每个都需要选择的话怎么做？这个其实更简单，都不需要visited数组了，只需要对每个元素，选择放入或者不放入即可。
39 数组中超过一半的数字
摩尔投票法。或者是利用快排的partition来找到中位数。
40 最小的K个数
那最小堆就可以了。也可以用partition来完成。
41 超大数据流中找到中位数
这个不会。
42 连续子数组的最大和
这题切记，我们计算的是当前这个数字之前的和，如果之前的和已经小于0了，那么就不要了，否则才加上去，然后取最大。
45 数组中拼接成最小的数字
任取两个数字，按照它们之间的大小进行排序，比较s1+s2拼接而成的字符串与s2+s1拼接而成的哪个大，就用哪个。
47 礼物的最大值
DP规划，没什么好说的，也没什么坑。
48 最长不含重复字符的字符串
用滑动窗口做的。方便简洁。MD之前用的hashmap恶心死了。
49 丑数
这主要是讲述了用时间换空间。
50 第一个只出现一次的字符
对，就是记录下每个字符出现的次数，然后对其进行操作即可。别想得太复杂了。
51 逆序对的个数
涉及到归并排序。