剑指Offer2 刷题复盘
面向复习用的剑指Offer第二版的刷题复盘
一些比较简单的题目就只分析了时间复杂度和空间复杂度然后跳过了。而且因为时间有限，有三四个题目没有写。
数组中重复的数字
思路：使用当前的下标作为hash，如果当前的下标对应的值和下标相等，说明位置正确；否则，将位置进行交换，比如[2, 3, 1, 0, 2, 5, 3]，下标为0处的2需要和下标为2处的1交换，然后再判断是否需要交换。
时间复杂度：遍历数组O(n)
空间复杂度：O(1)
二维数组中的查找
使用二分即可，从右上角到左下角。
时间复杂度：O(m+n)最坏情况是从右上角直接走到左下角
空间复杂度：O(1)
替换空格
思路：不要使用replace方法（如果需要使用的话，replace("\\s")表示替换一个空格）。初始化一个长度为三倍的数组存放字符，挨个放入。
时间复杂度：O(n)
空间复杂度：O(n)
从尾到头打印链表
思路：使用额外的栈空间保存
时间：O(n) 空间O(n)
重建二叉树
思路：使用前序遍历+中旬遍历的性质。
构建一个hash表，存放中序遍历中每一个元素对应的下标
然后依次遍历前序遍历的每一个元素，找到中序的下标，分成两个部分。以当前的前序遍历的元素为根节点，左右分成的子数组作为左右子树，依次递归。
时间：O(n) 空间：O(n) 递归的深度为n，同时hash占用了额外的空间
使用两个栈实现队列
思路：stack1 用于保存输入的数据，stack2用于保存输出的数据。如果stack2不为空，优先从stack2中获取内容；如果stack2为空，将stack1中所有的数据都放到stack2中。
时间复杂度：
插入：O(1) 删除O（1）：每个元素只会被插入和弹出一次
空间复杂度：O(n)
旋转数组的最小数字
思路如下：
时间复杂度：最坏的情况数组的全部数字相同O(n)，平时的情况O(logn)
空间复杂度：O(1)
二进制中1的个数
思路：
方法一：使用向右位移的方式计算1的个数
方法二：因为n&n-1实际上是将n的最右边的一个1设置为0，每次迭代的时候都进行计数。因为每一次迭代都是将一个1设置为0
n & n-1同样也可以用作判断当前的n是否是2的正整数幂。
数值的整数次方
思路：
使用幂相乘的机制，将n分解成二进制的形式
需要注意一个点，如果当n为负数的时候，而且是Integer.MIN_VALUE，取反可能会造成越界。这个时候需要使用long保存数据
时间：O(n)
打印从1到最大的n位数
需要考虑大数的情况。在这种情况下，需要去掉前导零。
前导零，通过substring去除。使用全局变量nine记录输出中的9的个数。当 009 -> 010时，nine++，此时n - start == nine ，需要移动start--，这样在后续string中 010 -> 10
调整数组顺序使奇数位于偶数前面
思路：利用快速排序partition的思路
时间：O(n)
树的子结构
思路：
定义dfs为同时比较Tree A和B的方法。
如果B == null，说明B已经比较完成，return true
（B != null）时，A==null 说明结构不相同 return false；
A != null && A.val != B.val 数值不同 return false
继续比较左和右节点
2. 因为空树不是任何树的子结构，所以return false。树B可能是当前的根节点的子结构，也可能是右子树的子结构，或者是左子树的子结构，所以要递归讨论。
时间复杂度： A的节点数量为M，B的为N O(MN)
空间复杂度：O(M) 退化到链表
二叉树的镜像
思路：在递归的过程中直接交换两个节点的位置
时间复杂度：O(M)
对称的二叉树
思路：花开两朵，相当于是完全相反的搜索方向
时间：O(N)
空间：O(N)如果当前的二叉树变成链表
包含min函数的栈
思路：使用两个栈
Stack1，用于正常存储数据；Stack2：如果存入的值小于栈顶，则放入。pop正常弹出，如果当弹出的数据和Stack2上面的相等，取出Stack2栈顶的值
栈的压入和弹出序列
思路：使用一个辅助栈的结构，这个结构用于存储存入的数字。我们可以遍历pushed数组，一遍遍历一遍存储数据到stack中，如果stack栈顶的元素和popped，指针指向的元素相同，则需要popped，同时指针指向下一个位置。如果没有意外，将会stack清空。没有清空就错误。
时间：O(N)
空间：O(N)
二叉搜索树
思路：只有中序遍历才能够构造一个有序的链表。考虑将连接前后节点的逻辑写在两个递归之间，是因为，当第一个递归回溯时，会回溯到根节点，此时根节点为cur，左节点为pre，这样就可以协程有序的链表。
最长不含重复字符的子字符串
思路：通过hashmap记录每一个元素的位置，后续出现重复就要更新位置。使用start表示当前的字符串的开始，如果从map中获取的重复的字符的位置在start之后，说明start内部存在重复的元素，然后将start更新为这个重复的字符的下标+1.
丑数
思路；这题和埃氏筛的思路比较类似，一个丑数只能由低维的数字x产生：2x，3x，5x。每次取这些数字中的最小值，可以保证丑数生成的顺序。
首先使用动态规划的方式构建一个dp数组，数组的第一个丑数就是1，然后使用a b c三个指针指向0的位置，dp[a], dp[b]，dp[c]分别乘以2 3 5，就是后续丑数的值。其中取最小值，放到当前下标为i的值，然后更新对应的a b c。
缺失的数字
思路：不多逼逼，直接猜。使用二分法。因为是一个排序的从0到n-1的数组，写几个例子就知道，使用一个指针指向下标为0，另外一个指针指向下标为nums.length-1，计算出二者的中间的下标mid。如果nums[mid] == mid，缺失的值在[mid + 1, end]，否则则是在[start, mid - 1]。然后while的退出条件是i <= j，因为当数组只有一个元素时，也需要遍历一次。
二叉树的最近公共祖先
使用递归，递归的参数表示当前的root，需要寻找的p和q。递归的方法表示在当前的root的左子树或者右子树中是否找到了p或者q。因为p可能在左子树，也可能是q在左子树，或者p在右子树，q在右子树，为了避免重复编码，我们可以直接携带这两个参数。
递归出口：
root == null 已经访问完成左子树或者右子树，但是找不到p或q，返回null
root = q || root == p 说明找到了其中一个，直接返回root
返回值的情况：
left == null && right == null：说明当前root的左右子树没有q和p
left == null && right != null 当前的右子树包含p或者q
left != null && right == null 当前的左子树包含p或者q
这两种情况都网上返回，碰到left 和right同时不为空即可
4. left 和 right 都不为空 找到root 返回
时间：O(N) 空间：O(N)
二叉搜索树的最近公共祖先
相对于上一题，就是将树改成了BST。针对BST可以利用它的性质，如果两个节点的值都小于root的值，递归左子树；都大于递归右子树。如果不满足这两种情况，说明分别在root的左右两边。返回root。而且不需要判断空，因为不会走到空节点
不用加减乘除做加法
这道题只能使用位运算解决。但是可以利用位运算的性质，将a+b分解成n（非进位和）和c（进位）。
具体代码如下：
时间复杂度：虽然和数字的位数有关，但是最大32位，所以是O(1)
扑克牌中的顺子
这道题主要是一个观察的规律：
如果能够组成顺子，不要出现重复的牌
同时最大的牌减去最小的牌小于5（如果大于等于5，没有癞子可以填）
时间：O(NlogN)排序耗时，但是N = 5，O(1)
队列的最大值
使用一个队列queue用于存放进入队列的数字，使用deque用于存放当前的最大值。
push：存value入queue，如果当前的deque的队尾的值小于value，一直清空到大于等于为止，然后存入deque
pop：从queue中移除，如果移除的值等于deque，移除deque的值。
n个骰子的点数
（主要还是参考一下K神的解析吧..）
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/
代码如下：
和为S的连续正数序列
使用两个指针i和j，i表示当前的子数组的起始，j表示结束，如果[i,j]的和sum小于target，j向右移动，并且加到sum中；如果sum > target不能继续移动j，需要减去i，然后再判断。while出口就是i和j相等，此时已经相当于把target除以二
时间复杂度：O(N)
求1+2+..+n
这道题不能使用迭代的方式实现，只能使用递归。递归的话条件出口if改写成&&，只有当n>1时才回去执行递归。
字符串转整数
