题三 数组中的重复数字
题目一
要求算法能在时间复杂度O(n)，空间复杂度O(1)的情况下，输出一个数组中的重复数字。我们很容易想到一个时间复杂度O(n)，空间复杂度O(n)的做法。如何完成空间复杂度为O(1)?
题解：
- 顺序遍历数组，如果下标i和值m相同，说明这个位置没有重复，继续向后。
- 如果遇到了，下标i和值m不同，那么比较m和下标为m的值是否相等，如果相等，说明m这个值重复。
- 如果不相等，就把m和下标为m的值交换，这样在后面如果又遇到这个值，就可以进行第2步，从而判断是否重复。
题目二
一个长度为n+1的数组，其中数字的范围为1-n，故肯定会有重复。请找出任意一个重复值，但不得改变数组。
很显然，有一个时间复杂度O(n)，空间复杂度O(n)的解法。但，如果要求空间复杂度为O(1)呢？
题解：
使用二分查找的思路，对每一半$\phi$的上标1-m，遍历总数组一遍，判断数组中的数属于1-m的总数，是否大于m，若大于，下次从这里开始二分，否则从另一半开始二分。
此方法，空间复杂度O(1)，但空间复杂度O(nlog(n))，所以属于牺牲时间换空间。还有另外一种解，归并排序，然后再遍历一遍，判断下一个是否与上一个重复，空间时间复杂度均与上面的方法相同。
题四 二维数组中的查找
在二维数组中，每一行都按照从左到右递增的顺序，每一列按照从上到下递增的顺序。查找是否存在，一个数n。
题解：很显然，应该从数组第一行的最后一个数字开始考虑，如果此数字就已经大于n，它所在的列是不可能包含n的。若大于n，则考虑这一列前面的列。若小于n，向这一列下方考虑：若遇见n，则结束；若遇到了x个比n小的数后，发现一个比n大的数，则在接下来的遍历中，不需要考虑，x行及之前行中的数了。若没有遇到比n大的数，则此数组没有n。
题五 替换空格
前提知识：用同样的内容初始化数组和指针，会得到不同的数组和相同的指针指向，因为指针是由常量字符串初始化得到的。
将字符串中的空格换为3个其他字符。
题解：显然可以新建一个字符串。如果要求在原字符串上修改，则应该先扫描一遍，然后根据对应的移动数，进行字符的移动。同样在遇到，合并两个数组到其中一个这样的题目上时，我们也应该采用从后向前的方法，来减少移动次数。
题六 打印链表
反向输出链表，没啥好讲的。
题七 重建二叉树
根据前序和中序序列构建二叉树。
题解：可按照递归的方法，每次通过限定index范围来构建左子树和右子树。
这里比较容易错的地方是：1.递归结束的条件：当前前序序列中无其他节点；2.构建左子树要满足：此根节点左侧还有点；3.构建右子树要满足：此根节点右侧还有点。
题八 二叉树的下一个节点
给定一个二叉树和一个节点，找到中序序列中其下一个节点。简单分为三种情况分析，没啥好说的。
题九 用两个栈实现队列
很显然，用一个栈来存储输入，一个栈来控制输出。当要求输出时，先判断输出栈是否为空，如果为空，则把输入栈的内容全部pop到输出栈里面。这样输出就和队列相似了。
用两个队列来实现栈也很简单，在每次pop的时候，把除了最后一个值以外的值pop到另一个队列中，然后把最后一个值输出即可。
题十 斐波那契数列
普通要求的斐波那契数列递归写法很简单，但是效率很低，是以n的指数级展开。我们很显然可以想到一个从0向后顺序算下去的方法，时间复杂度为O(n)。很好，但是，书上还给出了一种O(log(n))的方法，一个斐波那契数列的矩阵乘法性质。具体解释可以看这里。
书中提到了青蛙跳台阶问题。如果一个青蛙每次可以跳1或2次，那么跳到第n个台阶有多少种跳法？令f(n)为跳n个台阶的方法，有f(n)=f(n-1)+f(n-2)，因为这正好和可以跳的次数符合。但是此问题的f(0)=1。此外，如果每次青蛙能跳任意台阶呢？我们易证$f(n)=2^{n-1}$。
另外，书中还提到了矩形填充的问题，也是一个斐波那契数列问题。
题十一 旋转数组的最小数字
这题只要把三种情况列出来就知道怎么写了。也趁这个机会复习了下搜索和排序。
题十二 矩阵中的路劲
在一个二维数组中找到一个符合指定字符串的路劲，要求不能重复使用一个点。
这题很显然使用dfs来做。复习到的知识点：动态初始化二维数组。我把[row*cols+col]写成了[row*rows+col]，调试了老半天也过不了，sad。。。
题十三 机器人的运动范围
也是个很简单的dfs，没啥可说的。
题十四 剪绳子
有一根n长的绳子，可以把它剪成任意的m段，怎样剪能使得他们的乘积最大？书中首先给出了动态规划的做法。动态规划做法的关键在于，由于递归做法(f(n)=max(f(i)*f(n-i)))会有很多的子问题，所以我们从下到上开始，从而得到f(n)。书中的第二种做法是最优贪心：当剩余长度大于4时尽可能剪长度为3的绳子，否则剪长度为2的绳子。为什么这种贪心能达到最优呢？
我们首先易得$n<=4$时最优解法。当$n>=5$时，令$g(n)=a\times(n-a)>n$，得到$(a-1)n-a^2>0$，显然为了使得不等式成立，有$a>1$。因此$g(n)$为递增函数，最小值在$n=5$获得，可得$5(a-1)-a^2>0$，解此方程式得$a=2,3$。又因为$2(n-1)<=3(n-3)$，所以我们可知，当绳子长度长于4时，我们尽量剪3长度的绳子，就可得到最优解。
从这一题我们可以得知，如果一个最优解问题可以划分成为若干个子问题，且子问题中还有重叠的更小的子问题，我们就可以考虑用动态规划并从下向上求解。我们也可以尝试使用贪心算法，但是要给出最优的证明。
题十五 位运算
输出一个数二进制中的所有1。要考虑到负数移位的死循环问题，所以书中提出了一种移位相与的常规写法。然后又写了一个相减再与的写法，用到了这样一个思想：把一个整数减去1之后再和原来的数做位与运算，结果相当于把原来的数的最右边的1变成0。感觉在中很难随时想到，还是常规写法好想。
题十六 数值的整数次方
这题主要是考察代码的鲁棒性。应该从三个方面考察：功能测试，边界测试，错误测试。像是这题应该考虑底数为0指数为负的错误情况，指数为负数的边界情况，以及功能测试。折半求指数乘积的方法能够降低算法的复杂度。
题十七 打印从1到最大n位数
这题要注意大数问题，可以使用字符串来实现。同时一个输出全排列的方法可以提高算法的效率。
题十八 删除链表的节点
题目一 在O(1)的时间里删除链表节点
在O(1)的时间里删除一个指针节点，给定头指针和该指针节点。
我们可以用当前指针节点代替下一个节点，然后删除下个节点即可完成O(1)的做法，只是当我们要删除的是最后一个节点的时候，只能先遍历到先前节点，然后再进行删除。
题目二 删除链表中的重复节点
使用三个指针pre,head,next即可完成删除，只不过需要考虑删除的是否包括头结点这个问题。while的判断条件一开始我写成了while(p->next!=nullptr)，这样会造成错误，因为p有可能会被赋值成nullptr。另外，现行方法都没法满足删除后包括pre节点的重复判断，比如122111最后只会输出1，而不是nullptr。因此，在我的方法中，在删除重复的节点后，如果pre节点不为空，p节点会回退一步，这样就解决了这个问题。
题十九 正则表达式匹配
这一题很有意思，用状态机模式来完成了正则表达式，值得研究。
题二十 先留在这里
题二十一 将数组中的奇数全移到偶数前
书中这题的要求和题目一样，这样的话，直接从左和右边向中间靠近判断即可。但是牛客网的oj上还要求偶数之间，奇数之间的相对顺序保持一致，这样的话，用冒泡排序，每次把最左边的数字确定即可。
题二十二 链表中倒数第k个节点
很显然，面试官是不会接受遍历两次这种做法的。那么如何一次遍历就完成这个操作呢？我们可以在第一个指针走出k-1步后，使第二个指针指向开头，并与第一个指针同步向后移动。这样第二个指针最后指向的就是目标节点。我们还要考虑几个边界情况：1.头指针为空；2.k超出链表范围；3.k为0；
题二十三 链表中环的入口节点
首先，要判断有无环，当一个每次走两步的指针和一个每次走一步的指针相遇的时候，链表显然存在环。然后，我们来找入口节点：让一个指针先走环大小的步数，这样，两个指针相遇的点就是入口节点。那么，怎么找到环的大小呢？让判断环相遇的指针，一个留在原地，一个每次一步地继续走，这样重新相遇的时候，就可以知道步数。我们还要考虑边界情况：1.头指针为空；总之，这个方法很巧妙啊，自己想不知道要想到什么时候。
题二十四 反转链表
很显然，用两个指针和一个辅助指针就能在一次遍历后完成反转。我们要考虑这样几个边界情况：1.头结点为空；2.只有一个节点。
题二十五 合并两个排序的链表
以单调不减的顺序合并两个单调递增的链表。很显然，用两个指针就可以完成操作。我们需要考虑的边界情况：1.一个链表为空；2.两个全为空；我使用了循环来实现，书中用的是递归。看了下，还是递归简单一点。
题二十六 树的子结构
题三十二 从上往下打印二叉树
题目二
我们显然可以使用队列来实现，推广来说，不仅是层次遍历二叉树，只要是BFS，我们都可以用队列来实现。
要求从上向下打印二叉树，每层有个换行。咋实现呢？书中给出方法是用两个变量来记录。一个代表当前层，如果当前层的剩余数目还没有打印完，那么增加的分支就都是下一层的，依次类推。
题目三
要求用之字形的顺序打印二叉树。我想的方法是，判断当前是奇数还是偶数行，如果是奇数，那么正常输出，如果是偶数，把输出存储在栈中，等当前行结束后，再统一输出。通过了测试。书上给的则是另外一种方法，
题三十五 复杂链表的复制
好吧，你要让我想一个O(n)时间内，不用牺牲空间可以复制复杂指针的算法，我还真想不出来。老老实实看书吧，把新的节点都连到老节点的下一个，链接完两种指针后，再拆开就可以了。
题四十一 数据流中的中位数
好久没复习，对这题的印象就只有用堆了。先想想看能不能想起来！
You get it? 没错，就是维护一个最大堆一个最小堆，然后不断用堆顶的数字相互移动来维持数字的平衡，这样我们就能从数据流中瞬间得到中位数啦。
题四十三 整数中1出现的次数
很直接的想法：模十，如果结果为1，代表个位为1。而后，除以十即可循环判断各个位了。
题四十四 数字序列中某一位的数字
这一题需要分析各种位数的全部情况有多少种，这样就可以知道target是几位数，从而推出结果。想法很直接，但是写的很艰难，很多corner case。
题四十五 把数组排成最小的数
这题的关键在于证明custom sort能满足题目要求：也就是说如果 A cc B > B cc A (cc -> concatenate)，那么A应该排在B的后面。书中从传递，自反，对称三个性质证明了这个要求，传递性的证明稍微复杂，总体very decent~.
题四十六 把数字翻译成字符串
很直观的dp。
题四十七 礼物的最大价值
这题如果用dfs来做的话，会超时。我们可以换个思路，用循环来做，用二维dp数组来表示到当前点能到达的最大价值。这样就节省了很多递归调用的开销。
题四十八 最长不含重复字符的子字符串
这也是很经典的一题了，需要用map来记录当前char是否重复，如果重复就需要reset起点。有一个点需要注意的是，只有当重复的char的index在当前起点之后才需要reset。
题四十九 丑数
这题需要被highlight。基本思路是顺序生成丑数数列。怎么生成呢？其实就是为2，3，5分别维护一个队列。然后每次都三个中取一个最小的数，来做丑数数列的下一个。
题五十 数组中的逆序对
这题需要被highlight。这题的思路也很巧妙，使用merge sort来解，对每对array来说，用和merge sort一样的判断顺序就可以把所有的逆序对标记出来了。
题五十二 两个链表的第一个公共子节点
有了倒数第k个节点这个思路过后，这个题就最优解就可以想到了。我们先开始一边遍历并计数，如果最后两个指针相同，那么证明有公共点。那么根据计数的差别，我们先让两个指针步数同步（离终节点距离相同），这样就能判断第一个公共点了。
但是还有种幺蛾子情况我们需要考虑，如果链表是有环的呢？我们必须要先问清楚面试官，如果有环，我们就要使两个指针前进的步数不同，这样如果相遇的话，就是相交的。我们把这个点存起来，可以根据判断得到步数相差，从而得到第一个公共子节点（环的入口节点）。
题五十六 数组中数字出现的次数
这题值得留下姓名。注意出现了两次这个关键点，两次用xor就可以抵消了。那关键剩下两个数字被xor在一起了怎么办呢？我么可以根据他们不同的某一位digit，把全部数分成两组。然后分别在两组里面xor就可以啦。天啊，这个想法太完美了。
题五十六+ 数组中数字出现的次数 II
这题也值得留下姓名！。 哈哈，xor是行不通了。但是我们可以统计每一位数字出现的个数，如果能被三整除说明target的这一位是0，否则是1。
题五十七 和为s的两个数字 & 和为s的连续正数序列
看到排序好的序列，我们就要敏感地意识到可以用滑动窗口。
题六十 n个骰子的点数
这题用递归求解太慢。可以考虑用循环，重复利用两个大小为maxv+1的数组，每一次筛筛子前，清空当前要用的数组，然后dp_now[n] = dp_last[n-1] + … + dp_last[n-6]。 这样，我们就可以用dp求解出来啦。
题六十一 扑克牌中的顺子
这题，直观想法是，如果sequence没有超过两个的skip number的话，就可以填补成顺子。但是答案中的想法，更直接：如果max-min (not joker) > 2的话就肯定不是顺子啦。
题六十二 圆圈中最后剩下的数字
这题值得留下姓名。不懂这题为什么是easy，需要推一个很离谱的递推式。
设p(x, m, n)为从n个数中取走第m个数之后，原来坐标为x的数，现在的坐标。
可以得出, p(x, m, n) = (x - (m-1)%n - 1) % n, 我们把(m-1)%n简化为k后可得p(x, m, n) = (x - k - 1) % n。
那么可知，p的逆运算为p’(x, m, n) = (x + k + 1) % n。
设f(n, m)为从n个数中不停去掉第m个后，最后一个数字的坐标。
设f’(n-1, m)为从n个数中去掉第一个m之后，不停去掉剩下的第m个数后，最后一个数字的坐标。
则f(n, m) = f’(n-1, m)
那么f’(n-1, m) = p’(f(n-1, m)) = (f(n-1, m) + k + 1) % n = (f(n-1, m) + m) % n
所以f(n, m) = (f(n-1, m) + m) % n
题六十四 求1+2+…+n
这题就tm离谱。1
boolean res = (n != 0) && ((n += sumNums(n-1)) > 0);