LeetCode总结 -- 树的构造篇

这篇总结主要介绍树中比较常见的一类题型--树的构造。其实本质还是用递归的手法来实现，但是这类题目有一个特点，就是它是构建一棵树，而不是给定一棵树，然后进行遍历，所以实现起来思路上有点逆向，还是要练习一下。LeetCode中关于树的构造的题目有以下几道：
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree
Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

先来看看最简单的Convert Sorted Array to Binary Search Tree，数组本身是有序的，那么我们知道每次只要取中点作为根，然后递归构建对应的左右子树就可以了，递归的写法跟常规稍有不同，就是要把根root先new出来，然后它的左节点接到递归左边部分的返回值，右节点接到递归右边部分的返回值，最后将root返回回去。这个模板在树的构造中非常有用，其他几道题也都是按照这个来实现。

接下来是Convert Sorted List to Binary Search Tree，这个跟Convert Sorted Array to Binary Search Tree比较近似，区别是元素存储的数据结构换成了链表，不过引入了一个重要的问题，就是链表的访问不是随机存取的，也就是不是O(1)的，如果每次去获取中点，然后进行左右递归的话，我们知道得到中点是O(n/2)=O(n)的，如此递推式是T(n) = 2T(n/2)+n/2，复杂度是O(nlogn)，并不是线性的，所以这里我们就得利用到树的中序遍历了，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。如此就能按照链表的访问顺序来构造，不会因此而增加找中间结点的复杂度。

最后是Construct Binary Tree from Preorder and Inorder Traversal和Construct Binary Tree from Inorder and Postorder Traversal，这个方法还是跟上面的题目一样来构造，主要问题是如何将节点劈成左右两部分进行递归，Construct Binary Tree from Preorder and Inorder Traversal就是利用前序遍历跟一定在第一个，而中序遍历又可以根据根来把元素劈成两块，类似的Construct Binary Tree from Inorder and Postorder Traversal是根据后序遍历最后一个是根的特点，然后利用中序遍历劈块，原理是一样的，最后的实现大家可以参考一下代码。

这篇总结主要介绍了LeetCode中四个树的构造的题目，比较统一的思路就是在递归中创建根节点，然后找到将元素劈成左右子树的方法，递归得到左右根节点接上创建的根然后返回。方法还是比较具有模板型的，不熟悉的朋友可以练习一下哈。

Min Stack -- LeetCode

原题链接: https://oj.leetcode.com/problems/min-stack/
这道题是关于栈的题目，实现一个栈的基本功能，外加一个获得最小元素的操作。正常情况下top，pop和push操作都是常量时间的，而主要问题就在于这个getMin上面，如果遍历一遍去找最小值，那么getMin操作就是O(n)的，既然出出来了这道题就肯定不是这么简单的哈。比较容易想到就是要追溯这个最小值，在push的时候维护最小值，但是如果pop出最小值的时候该如何处理呢，如何获得第二小的值呢？如果要去寻找又不是常量时间了。解决的方案是再维护一个栈，我们称为最小栈，如果遇到更小的值则插入最小栈，否则就不需要插入最小栈（注意这里正常栈是怎么都要插进去的）。这里的正确性在于，如果后来得到的值是大于当前最小栈顶的值的，那么接下来pop都会先出去，而最小栈顶的值会一直在，而当pop到最小栈顶的值时，一起出去后接下来第二小的就在pop之后最小栈的顶端了。如此push时最多插入两个栈一个元素，是O(1)，top是取正常栈顶，自然是O(1)，而pop时也是最多抛出两个栈的栈顶元素，O(1)。最后getMin只需要peek最小栈顶栈顶即可，所以仍是O(1)，实现了所有操作的常量操作，空间复杂度是O(n)，最小栈的大小。代码如下：

class MinStack {
    ArrayList<Integer> stack = new ArrayList<Integer>();
    ArrayList<Integer> minStack = new ArrayList<Integer>();
    public void push(int x) {
        stack.add(x);
        if(minStack.isEmpty() || minStack.get(minStack.size()-1)>=x)
        {
            minStack.add(x);
        }
    }

    public void pop() {
        if(stack.isEmpty())
        {
            return;
        }
        int elem = stack.remove(stack.size()-1);
        if(!minStack.isEmpty() && elem == minStack.get(minStack.size()-1))
        {
            minStack.remove(minStack.size()-1);
        }
    }

    public int top() {
        if(!stack.isEmpty())
            return stack.get(stack.size()-1);
        return 0;
    }

    public int getMin() {
        if(!minStack.isEmpty())
            return minStack.get(minStack.size()-1);
        return 0;
    }
}

这道题在理清思路之后代码还是比较简单的，这里用ArrayList来实现栈，当然也可以用链表，不过对于时间复杂度要求比较高，所以重点是想出维护最小栈顶做法，属于比较考察站的性质的题目，是很不错的面试题目，在面经中也经常出现。

Find Minimum in Rotated Sorted Array II -- LeetCode

这道题是Search in Rotated Sorted Array的扩展，思路在Find Minimum in Rotated Sorted Array中已经介绍过了，和Find Minimum in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现，影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的。而现在因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就无法判断哪边有序，因为哪边都有可能有序。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，我们并不知道应该截掉哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况就会出现每次移动一步，总共移动n此，算法的时间复杂度变成O(n)。代码如下：

public int findMin(int[] num) {
    if(num == null || num.length==0)
        return 0;
    int l = 0;
    int r = num.length-1;
    int min = num[0];
    while(l<r-1)
    {
        int m = (l+r)/2;
        if(num[l]<num[m])
        {
            min = Math.min(num[l],min);
            l = m+1;
        }
        else if(num[l]>num[m])
        {
            min = Math.min(num[m],min);
            r = m-1;
        }
        else
        {
            l++;
        }
    }
    min = Math.min(num[r],min);
    min = Math.min(num[l],min);
    return min;
}

在面试中这种问题还是比较常见的，现在的趋势是面试官倾向于从一个问题出发，然后follow up问一些扩展的问题，而且这个题目涉及到了复杂度的改变，所以面试中确实是一个好题，自然也更有可能出现哈。

Find Minimum in Rotated Sorted Array -- LeetCode

这道题是Search in Rotated Sorted Array的扩展，区别就是现在不是找一个目标值了，而是在bst中找最小的元素。主要思路还是跟Search in Rotated Sorted Array差不多，还是通过左边界和中间的大小关系来得到左边或者右边有序的信息，如果左半边有序，那么左半边最小就是左边第一个元素，可以和当前最小相比取小的，然后走向右半边。否则，那么就是右半半边第一个元素，然后走向左半边。这样子每次可以截掉一半元素，所以最后复杂度等价于一个二分查找，是O(logn)，空间上只有四个变量维护二分和结果，所以是O(1)。代码如下：

public int findMin(int[] num) {
    if(num == null || num.length==0)
        return 0;
    int l = 0;
    int r = num.length-1;
    int min = num[0];
    while(l<r-1)
    {
        int m = (l+r)/2;
        if(num[l]<num[m])
        {
            min = Math.min(num[l],min);
            l = m+1;
        }
        else if(num[l]>num[m])
        {
            min = Math.min(num[m],min);
            r = m-1;
        }
        else
        {
            l++;
        }
    }
    min = Math.min(num[r],min);
    min = Math.min(num[l],min);
    return min;
}

有朋友可能注意到上面的实现还有第三种情况，就是左边界和中间是相等的情况，这道题目其实是不用发生的，因为元素没有重复，而Find Minimum in Rotated Sorted Array II这道题这考虑了元素重复的情况，这里只是为了算法更加一般性，就把那个情况也包含进来，有兴趣的朋友可以看看Find Minimum in Rotated Sorted Array II对重复元素的分析哈。

LeetCode总结 -- 二叉查找树篇

这篇总结主要介绍一个比较常见的数据结构--二叉查找树。二叉查找树既是一颗树，又带有特别的有序性质，所以考察的方式比较多而且灵活，属于面试题目中的常客。LeetCode中关于二叉查找树的题目有以下几道：
Validate Binary Search Tree
Recover Binary Search Tree
Unique Binary Search Trees
Unique Binary Search Trees II
Convert Sorted Array to Binary Search Tree
Convert Sorted List to Binary Search Tree

先来看看最基本的Validate Binary Search Tree，就是判断一个树是不是二叉查找树。比较简单而且明了的方法就是利用二叉查找树的中序遍历有序的性质，只要对树进行一次中序遍历，而其中的结点都满足有序即可，实现上就是维护一个前驱结点，每次判断前驱结点比当前结点要小。另一种方法是根据二叉查找树的定义来实现，保证结点满足它的左子树的每个结点比当前结点值小，右子树的每个结点比当前结点值大，实现上就是对于每个结点保存左右界，然后进行递归判断左右界不会违背即可。

Recover Binary Search Tree这道题目还是利用二叉查找树的主要性质，就是中序遍历是有序。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。主要考虑到就是出现违背的次数问题。这里有两种情况：
（1）如果是中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；
（2）如果是不相邻的两个元素被调换了，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。

Unique Binary Search Trees这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。这其实是一个卡特兰数的模型，所以按照公式进行实现就可以。而Unique Binary Search Trees II则不能用卡特兰数，因为要求出所有结果，所以还是得走递归遍历的过程，然后把生成树来的树接上。

Convert Sorted Array to Binary Search Tree和Convert Sorted List to Binary Search Tree则是属于二叉查找树的构造问题，针对两种不同数据结构数组和链表进行构造。其实方法都是一样，就是递归对窗口进行圈限，然后用中间的结点作为当前根，再递归生成左右子树。链表的构造要稍微绕一些，因为要通过中序遍历走到第一个结点，然后递进链表。

这篇总结主要介绍LeetCode中关于二叉查找树的题目，二叉查找树因为是基本数据结构加上有可利用的有序性质，还是在面试中相当常见的，对于性质理解要深刻，实现要熟练哈。

Maximum Product Subarray -- LeetCode

原题链接: https://oj.leetcode.com/problems/maximum-product-subarray/
这道题跟Maximum Subarray模型上和思路上都比较类似，还是用一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优，这是由于乘法的性质不像加法那样，累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。不过事实上也没有麻烦很多，我们只需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积和，这也是利用乘法的性质得到的。代码如下：

public int maxProduct(int[] A) {
    if(A==null || A.length==0)
        return 0;
    if(A.length == 1)
        return A[0];
    int max_local = A[0];
    int min_local = A[0];
    int global = A[0];
    for(int i=1;i<A.length;i++)
    {
        int max_copy = max_local;
        max_local = Math.max(Math.max(A[i]*max_local, A[i]), A[i]*min_local);
        min_local = Math.min(Math.min(A[i]*max_copy, A[i]), A[i]*min_local);
        global = Math.max(global, max_local);
    }
    return global;
}

这道题是一道很不错的面试题目，因为Maximum Subarray这道题过于常见了，所以可能大部分人都做过，这道题模型类似，但是又有一些新的考点，而且总体还是比较简单，无论是思路上还是实现上，又能考察动态规划，个人还是比较喜欢的哈。

LeetCode总结 -- 图篇

图的算法跟树一样是准备面试中必不可少的一块，不过图的方法很容易概括，面试中考核的无非就是两种搜索算法：深度优先搜索和广度优先搜索。LeetCode中关于图的问题有以下几个：
Clone Graph
Word Ladder
Word Ladder II
Longest Consecutive Sequence
Word Search
Surrounded Regions

先来看看最基础的Clone Graph，很简单就是要复制一个图，常见的两种搜索算法（深度和广度）都可以用，具体细节就不在这里解释了，不熟悉的朋友可以看看相关资料。建议大家还是两种都要练一练，因为在解决具体问题中这两种方法还是很常用的。

接下来的这些题都是基于图算法的应用，Word Ladder和Word Ladder II是比较典型的，看起来好像是字符串操作的题目，实际上这里得转换成图的角度来考虑，因为字符集比较小的缘故（26个小写字母），也就是说对于一个单词来说，改变其中一个字符可以有25条边（除去他自己），所以总共有（25*单词的长度L）条边。找到是否有满足一个单词转成另一个单词就是在这个图中找到一条路径。所以我们可以把问题转换成图用广度优先搜索来解决，找到即可停止。

Word Ladder是广度优先搜索的应用，而Longest Consecutive Sequence则是深度优先搜索的应用。题目要求是找出最长的连续整数串，如果把数字看成结点，与它相邻的整数连有边，那么找到最长的连续串就是在这个图中找最长路径。因为是最长路径，这里用深度优先搜索是比较适合的。

Word Search也是一道深度优先搜索的题目，是把上下左右相邻的结点看成有边联结，然后进行深度搜索就可以了，小细节是这里从每个点出发字符就可以重用，所以要重置一下访问结点。

Surrounded Regions要用一个图形学中很常用的填充算法：Flood fill 算法，其实本质还是一个深度优先搜索，跟Word Search一样是把相邻的上下左右看成连边，然后进行搜索填充。

图的问题其实本质都是两种搜索算法，难点主要在于对于具体问题如何想到转换成图的问题，然后用这两种搜索来解决，这也是算法中的一个分支，面试中也是常客哈。

LeetCode总结 -- 矩阵篇

矩阵（一般是二维数组）操作的题目在面试中考察基础coding的时候比较常见，一般来说不带有太多算法思想，纯粹就是二维数组下标的操作。虽然比较简单，不过还是比较能体现基本的实现能力。LeetCode中关于矩阵操作的题目有以下几个：
Spiral Matrix
Spiral Matrix II
Rotate Image
Valid Sudoku

Set Matrix Zeroes

前面三个题Spiral Matrix，Spiral Matrix II，Rotate Image思路比较类似，都是按照一定的规则在二维数组里面走下标。

Spiral Matrix就是按照螺旋的方式，按照右下左上的顺序，走到头就换方向。小技巧就是把这些螺旋分成层，然后知道区间照着走就可以。Spiral Matrix II也是一样的，不过是换成1到n^2的整数。

而Rotate Image也是比较类似的，主要是想清楚每一个点经过旋转之后的下表位置，然后还是分成层，一层层进行旋转即可。

Valid Sudoku是让我们判断一个Sudoku的盘是否合法，对于行和列的判断应该比较简单，就是1到9不重复出现即可，有点技巧的是对于每个九宫格的合法性判断，这里需要稍微斟酌一下才可以把代码写得比较通用简洁一些，大家可以看看Valid Sudoku中的实现哈。

最后我们来说说比较有技巧的Set Matrix Zeroes这道题。它是一个非常常见的题目了，也是cc150中的题目。看似一个非常简单的题目，就是如果矩阵如果有元素为0，就把对应的行和列上面的元素都置为0，但是却有层层的优化方法。时间复杂度基本都是O(m*n)，而空间复杂度却有很多可以优化的空间。最简单的思路是备份一个矩阵，然后照着原矩阵进行判断，有0则置对应列和行为0，这样空间是O(m*n)。而如果我们维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0，最后在进行一次赋值，这样时间复杂度不变，而空间复杂度只需要O(m+n)。再进一步优化，如果我们连布尔数组都不要，而用第一行和第一列来代替布尔数组，然后用两个变量来维护第一行和第一列的置0情况，这样就只需要O(1)的额外空间了。模型非常简单的一个题目，却有非常不同的答案，还是比较值得一考的题目哈。

这篇总结主要介绍了LeetCode中几个关于矩阵操作的题目，这种题目主要考点就是二维数组的下标操作，写代码的时候要思路清晰，才能保证bug free地实现。而有时候也会有像Set Matrix Zeroes这样模型比较简单，但是还是有一些考点的题目，大家还是要尽量考虑到最优解法。

LeetCode总结 -- 位运算篇

位运算一直编程和面试中的一个必须准备的主题。 不过现在面试中关于位运算的出现得不多，主要原因还是位运算太考察技巧了，很多时候很难在短时间内想出来，所以作为面试的题目显得有点太花时间了。LeetCode中关于位运算的题目有以下几道：
Single Number
Single Number II
Divide Two Integers
Pow(x, n)

先来说说Single Number， 这应该LeetCode中唯一一道纯粹用位运算解决的题目。题目本身要求是找出唯一一个在数组中出现一次的整数，而其他都会出现两次。这里利用到了位运算中异或的性质，就是两个相同的数进行异或会得到0，并且任何一个数与0的异或还是原数。利用上面的性质，只要把数组中的元素一一异或起来，因为出现两次的会互相抵消，最后会只剩下那个出现一次的整数，所以就搞定了。

对于Single Number II，上面的方法就没办法了，因为出现三次就不能利用异或的性质了，所以这个题目得使用另外的方法了。 算法是对每个位出现1的次数进行统计，因为其他元素都会出现三次，所以最终这些位上的1的个数会是3的倍数。如果我们把统计结果的每一位进行取余3，剩下的结果就会剩下那个出现一次的元素。这个方法对于出现k次都是通用的，包括上面的Single Number也可以用这种方法，不过没有纯位运算的方法高大上哈。

接下来看看位运算在Divide Two Integers和Pow(x, n)这道题中的应用，主要是利用任何一个整数可以表示成以2的幂为底的一组基的线性组合的性质，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。对于Divide Two Integers基于上面的性质以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k，然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度可以达到O(logn)，也就是位的数量。而Pow(x, n)也是使用同样的方法，把幂数n分解成2的幂数的基，然后进行依次平方然后求和。这个方法算是数值运算中的一个比较实用的方法，还是要熟练掌握。

这篇总结介绍了LeetCode中几个关于位运算的题目，虽然数量很少，不过思想上还是都挺有意义的，如果面试中遇到能提出位运算的解法还是能加分不少，所以位运算在有些题目中还是一把关键的武器。

LeetCode总结 -- 高精度篇

我们常见的一些基本的数据结构比如整型int或者浮点型float由于位数过多无法用内置类型存储，这时候我们就需要自己实现高精度的数据类型来进行存储和运算。这种问题在实际产品中还是比较实用的，所以相对来说也是面试中的常客。LeetCode中关于高精度的题目有以下几道：
Add Binary
Add Two Numbers
Plus One
Multiply Strings

Add Binary和Add Two Numbers是同一类型的题目，都是高精度中的加法运算，只是一个是二进制的，一个是十进制的，其实进制是无所谓的，代码基本可以统一起来用一种思路来实现。思路也很简单，就是从低位开始相加，一直维护进位就可以了。属于考察非常基本的数组操作，没有什么算法难度，主要看看coding实现能力。

Plus One也是一道常见的题目，他其实就是实现C++中++的运算符，因为只需要+1，所以其实比上面的题目更加简单。这道题的小陷阱就是它是用数组从高位到低位进行存储的，所以如果出现进位，那么需要重新分配空间，并给最高位赋1，其他位赋0即可。这里恰好引入一个点，就是高精度存储应该低位到高位存储还是反过来好，这也是面试中可能问到的问题。

Multiply Strings这道题是高精度的乘法运算，属于比较复杂的，需要对每一位的结果分别计算累加，其中的细节有点多，这里就不细说了，个人认为实现有点复杂，并不是很适合在面试中出现。

虽然说题目不多，但是这类题目的出现率却是非常高的，主要原因倒不是这种题目本身有很多的考点，而是它们特别好扩展，基本上来说问到这种题目，首先是考察一下coding能力，一般来说都是这种加减乘除的运算，接下来一定会是关于数据结构（或者说面向对象）的设计。这些题目的本身都是为高精度BigInteger服务的，面试官会问一些关于这个数据结构设计的问题，比如说如果让你来设计这个类，用什么数据结构来存（比如数组还是链表，各有什么利弊），需要哪些接口（构造函数，加减乘除运算等等），还有比如要设计构造函数，需要什么接口的构造函数（这里赋值构造函数，赋值运算符这些肯定是需要的，但是要注意必须提供对于常规类型比如int，long这些的接口，一个好的高精度类肯定是要对比它更弱的数据结构进行兼容的）。

上面我列举了一些可能在面试中会被继续考查的问题，也是一部分联想，像这种设计问题可以问得还是比较多的，也是非常常见的，大家可以自己多进行这种问题的准备和联想哈。

LeetCode总结 -- 树的性质篇

树的性质判断是树的数据结构比较基本的操作，一般考到都属于非常简单的题目，也就是第一道入门题，面试中最好不能有问题，力求一遍写对，不要给面试官任何挑刺机会。LeetCode中关于树的性质有以下题目：
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Balanced Binary Tree
Same Tree
Symmetric Tree

首先说说关于求树的深度的题目，最简单的是求最大深度Maximum Depth of Binary Tree，一般都是用递归实现。思路很简单，只需要对走到空结点返回0，然后其他依次按层递增，取左右子树中大的深度即可。Minimum Depth of Binary Tree稍微复杂一点，主要是要注意因为是取左右子树小的深度，但是有一种情况是不计入深度的，就是比如左子树彻底为空时，这种情况我们不会认为深度就是0，因为左边并没有叶子，按照定义我们是要找叶子结点的最小深度。所以需要对于左右是否为空做一个额外的判断。

求树的深度属于简单的题目，所以如果递归实现比较快的话，面试官可能会问非递归怎么实现，如果有时间的话还是得练习一下哈，原理跟LeetCode总结 -- 树的遍历篇是一致的。

Balanced Binary Tree是求深度的一道扩展题目，基本原理还是求深度。不过需要增加的环节是判断他是不是平衡树，因为深度是我们必须维护的量，如果选用额外的布尔变量来维护是否为平衡树也可以。不过这里可以利用深度大于0的性质，可以将平衡的树返回正常的深度值，而不平衡的则返回-1来进行区分，这样相当于用一个变量维护了想要的两种性质，代码实现也比较简单。

Same Tree也是比较基础的题目，和树的遍历时一样的，只是对两棵树同时做相同的遍历，然后进行一一比较，如果出现不同则返回false即可。

Symmetric Tree会稍微绕一点，不过想清楚跟Same Tree还是差不多，第一个不同点是要根据左右子树比较，其实就是把左右子树当成Same Tree中的两个树即可。第二个不同点是在递归过程中对于结点的左右子树进行互换比较，也就是左跟右比，右跟左比。

这篇总结主要提到了LeetCode中求树的一些基本性质的题目，这类题目比较简单，属于最低门槛题目，所以要力求bug free地一遍完成哈。

LeetCode总结 -- 树的求和篇

树的求和属于树的题目中比较常见的，因为可以有几种变体，灵活度比较高，也可以考察到对于树的数据结构和递归的理解。一般来说这些题目就不用考虑非递归的解法了（虽然其实道理是跟LeetCode总结 -- 树的遍历篇一样的，只要掌握了应该没问题哈）。 LeetCode中关于树的求和有以下题目：
Path Sum
Path Sum II
Sum Root to Leaf Numbers
Binary Tree Maximum Path Sum

我们先来看看最常见的题目Path Sum。这道题是判断是否存在从根到叶子的路径和跟给定sum相同。树的题目基本都是用递归来解决，主要考虑两个问题：

1）如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和是sum减去当前结点值得路径，只要有一个存在，那么当前结点就存在路径。

2）考虑结束条件是什么。这里的结束条件一个是如果当前节点是空的，则返回false。另一个如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

想清楚上面两个问题，那么实现起来就是一次树的遍历，按照刚才的分析用参数或者返回值传递需要维护的值，然后按照递归条件和结束条件进行返回即可。算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。

对于Path Sum II，其实思路和Path Sum是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量了。

Sum Root to Leaf Numbers这道题多了两个变化，一个是每一个结点相当于位上的值，而不是本身有权重，不过其实没有太大变化，每一层乘以10加上自己的值就可以了。另一个变化就是要把所有路径累加起来，这个其实就是递归条件要进行调整，Path Sum中是判断左右子树有一个找到满足要求的路径即可，而这里则是把左右子树的结果相加返回作为当前节点的累加结果即可。

变化比较大而且有点难度的是Binary Tree Maximum Path Sum，这道题目的路径要求不再是从根到叶子的路径，这个题目是把树完全看成一个无向图，然后寻找其中的路径。想起来就觉得比上面那种麻烦许多，不过仔细考虑会发现还是有章可循的，找到一个根节点最大路径，无非就是找到左子树最大路径，加上自己的值，再加上右子树的最大路径（这里左右子树的路径有可能不取，如果小于0的话）。我们要做的事情就是对于每个结点都做一次上面说的这个累加。而左子树最大路径和右子树最大路径跟Path Sum II思路是比较类似的，虽然不一定要到叶子节点，不过标准也很简单，有大于0的就取，如果走下去路径和小于0那么就不取。从分治的角度来看，左右子树的最大路径就是取自己的值加上Max(0，左子树最大路径，右子树最大路径)。这么一想也就不用考虑那么多细节了。而通过当前节点的最长路径则是自己的值+Max(0，左子树最大路径)+Max(0，右子树最大路径)。所以整个算法就是维护这两个量，一个是自己加上左或者右子树最大路径作为它的父节点考虑的中间量，另一个就是自己加上左再加上右作为自己最大路径。具体的实现可以参见Binary Tree Maximum Path Sum。

这篇总结主要讲了LeetCode中关于树的求和的题目。总体来说，求和路径有以下三种：（1）根到叶子结点的路径；（2）父结点沿着子结点往下的路径；（3）任意结点到任意结点（也就是看成无向图）。这几种路径方式在面试中经常灵活变化，不同的路径方式处理题目的方法也会略有不同，不过最复杂也就是Binary Tree Maximum Path Sum这种路径方式，只要考虑清楚仍然是一次递归遍历的问题哈。

LeetCode总结 -- 一维数据合并篇

合并是一维数据结构中很常见的操作， 通常是排序， 分布式算法中的子操作。 这篇总结主要介绍LeetCode中关于合并的几个题目：
Merge Two Sorted Lists
Merge Sorted Array
Sort List
Merge k Sorted Lists

我们先来看看两个有序一维数据的合并， 这里主要是要介绍链表的合并操作， 不过因为一维数组的合并也比较简单， 而且与链表有比较性， 就顺便在这里列举一下。 Merge Two Sorted Lists就是要求合并两个有序链表， 一般来说合并的思路就是以一个为主参考， 然后逐项比较， 如果较小元素在参考链表中， 则继续前进， 否则把结点插入参考链表中， 前进另一个链表， 最后如果另一个链表还没到头就直接接过来就可以了， 思路和实现都比较简单， 最好力求一遍过哈。 Merge Sorted Array也是一样的思路， 只是数据结构换成了一维数组， 所以插入操作比链表要麻烦一些， 这里相当于从尾部开始， 然后数字一个个按照位置填入， 插入操作在这里就不明显了。 可以看出虽然思路近似， 但是数据结构不同， 因为操作不同， 实现细节还是比较不一样的， 都得熟练掌握哈。
有了上面合并两个链表（或者数组）我们就可以进行归并排序了， 也就是Sort List这道题目。 对于链表， 用Merge Two Sorted Lists作为合并的子操作， 然后用归并排序的递归进行分割合并就可以了， 这里就不说排序的具体细节了， 会有专门的排序总结篇哈。

最后我们来说说最重要的也是最实用的一个题目Merge k Sorted Lists。 为什么说他实用是因为现在分布式系统很多， 而且也很强调MapReduce或者Hadoop的技术， 这个题目就是分布式计算的一个常见操作。 比如说来自不同client的有序数据要在central server上面进行合并。 这个问题有两种做法：
第一种就是利用上面的Merge Two Sorted Lists对k个链表先进行两两合并， 然后再上一层继续两两合并， 直到合成一个链表。 根据Merge k Sorted Lists中的分析， 时间复杂度是O（nklogk）, 空间复杂度是O（logk）。
上面这种做法是利用分治然后进行合并的方法， 接下来这个方法用到了堆的数据结构。 思路是维护一个大小为k的堆， 每次取堆顶的最小元素放到结果中，然后读取该元素对应的链表的下一个元素放入堆中。 因为每个链表是有序的， 每次又是去当前k个元素中最小的， 所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。 这个算法每个元素要读取一次，即k*n次，然后每次读取元素要把新元素插入堆中要O（logk）的复杂度，所以复杂度是O(nklogk)， 跟第一种方法是一样的。
两种方法不同的数据结构和类型， 都非常具有代表性， 个人觉得都很有意思哈。

合并算是链表中比较典型的操作， 也能够连续地问出比较连贯的一些题目， 扩展性非常好， 既可以考察基本数据结构的操作， 又可以看看对于算法和更多数据结构的理解， 是一个不错的面试话题。

LeetCode总结 -- 数值计算篇

数值计算在工业界是非常实用而且常见的具体问题, 所以在面试中出现频率非常高, 几乎可以说是必考题目。 LeetCode中关于数值运算的有以下题目：
Palindrome Number
Reverse Integer
Sqrt(x)
Pow(x, n)
Divide Two Integers
Max Points on a Line
在LeetCode中， 关于数值运算的题目分为三种类型， 下面将进行一一讲解。

第一种类型是最简单的， 就是对整数进行直接操作， 一般来说就是逐位操作， 比如反转， 比较等。 LeetCode中这类题目有Palindrome Number和Reverse Integer。 这类题目通常思路很清晰， 要注意的点就是对于边界情况的考虑， 对于数值而言， 主要问题是对于越界情况的考虑。 实际上越界问题是贯穿于所有数值计算题目的常见问题， 下面大多问题都会强调这点。
在Palindrome Number中因为只是进行判断， 并不需要修改数字， 所以没有越界问题。 思路比较简单， 就是每次取出最高位和最低位进行比较， 直到相遇或者出现违背条件（也就是不相等）即可返回。 对于Reverse Integer因为需要对数字进行反转， 所以需要注意反转后的数字可能会越界。 对于越界一般都是两种处理方法， 一种是返回最大（或者最小）数字， 一种则是抛出异常， 这个可以跟面试官讨论， 一般来说， 面试只要简单的返回最大最小或者dummy数字就可以了， 但是处理和检查这种corner case（也就是越界）的想法一定要有和跟面试官讨论。

第二种题型是算术运算的题目， 比如乘除法， 阶乘， 开方等， LeetCode中这类题目有Sqrt(x)， Pow(x, n)和Divide Two Integers。 这种题目有时候看似复杂， 其实还是有几个比较通用的解法的， 下面主要介绍三种方法：
（1）二分法。 二分法是数值计算中很常用和易懂的方法。 基本思路是对于所求运算进行对半切割， 有时是排除一半， 有时则是得到可重复使用的历史数据。 Sqrt(x)就是属于每次排除一半的类型， 对于要求的开方数字进行猜测， 如果大于目标， 则切去大的一半， 否则切去大的一半， 原理跟二分查找是一样的。 Pow(x, n)则是属于重复利用数据的类型， 因为x的n次方实际上是两个x的n/2次方相乘， 所以我们只需要递归一次求出当前x的当前指数的1/2次方， 然后两个相乘就可以最后结果。 二分法很明显都是每次解决一半， 所以时间复杂度通常是O（logn）量级的。
（2）牛顿法。 这种方法可以说主要是数学方法， 不了解原理的朋友可以先看看牛顿法-维基百科。 Sqrt(x)就非常适合用牛顿法来解决， 因为它的递推式中的项都比较简单。 Pow(x, n)当然原理上也可以用牛顿法解答， 但是因为他的递推式中有项是进行x的开n次方的， 这个计算代价也是相当大的， 如果为了求x的n次方而去每一步求开n次方就没有太大实际意义了， 所以对于这种题我们一般不用牛顿法。
（3）位移法。 这种方法主要基于任何一个整数可以表示成以2的幂为底的一组基的线性组合， 对一个整数进行位数次迭代求解， 因为复杂度是位数的数量， 所以也跟二分法一样是O（logn）量级的。 Pow(x, n)和Divide Two Integers就是比较典型可以用这种方法解决的题目。 对于Pow(x, n)可以把n分解成位， 每次左移恰好是当前数的平方， 所以进行位数次迭代后即可以得到结果， 代码中很大的篇幅都是在处理越界问题， 而关于逐位迭代代码却很简短。 Divide Two Integers同样把结果分解成位， 每次对除数进行位移并且减去对应的除数来确定每一位上的结果。 这种方法可能理解起来没有二分法那么直观， 还是要消化一下哈。

第三种题目是解析几何的题目， 一般来说解析几何题目的模型都比较复杂， 而且实现细节比较多， 在面试中并不常见， LeetCode中也只有Max Points on a Line是属于这种题型。 这种题目没有什么通法， 主要就是要理清数学和几何模型， 比如Max Points on a Line中主要是理解判断点在直线的判断公式， 然后进行迭代实现。 实现细节还是比较多的， 需要对一些边界情况仔细考虑。

这篇总结主要列举了LeetCode中关于数值计算的题目， 介绍了这类问题的主要考点（比如越界判断）和常用的几种实用方法， 总体感觉这类问题是在面试中比较难很快写对的题目， 因为有一些边界情况和数值实现的细节。 因为出现频率很高， 还是需要对这类题目重点练习哈。

LeetCode总结 -- kSum篇

这篇总结主要介绍LeetCode中几道关于求kSum的题目， 主要要求是在数组中寻找k个数的和能否达到目标值。 LeetCode关于kSum的主要题目有：
Two Sum
3Sum
3Sum Closest
4Sum
首先从Two Sum开始， 这道题目提供了后面k>2的题目的基本思路， 也是最常考到的题目（亚马逊的面试对这道题算是情有独钟了）。 主要有两种思路， 一种是利用哈希表对元素的出现进行记录，然后进来新元素时看看能不能与已有元素配成target， 如果哈希表的访问是常量操作，这种算法复杂度是O(n)。 另一种思路则是先对数组进行排序， 然后利用夹逼的方法找出满足条件的pair， 算法的复杂度是O(nlogn)。 两种方法都比brute force的O(n^2)要优， 具体可以参见题目Two Sum的具体分析。 因为这道题模型简单， 但是可以考核到哈希表等基本数据结构和排序等基本算法， 所以是面试中的常客。
接下来是3Sum和3Sum Closest， 3Sum是使用Two Sum的第二种方法作为子操作， 然后循环每个元素， 寻找剩下的元素满足条件的pair即可。 3Sum Closest和3Sum很类似， 只是要多维护一个最小的diff， 保存和target最近的值。 算法的复杂度是O(n^2)， 这道题使用Two Sum的第一种方法并不合适， 因为当出现元素重复时用哈希表就不是很方便了。
最后是4Sum， 这道题的比较优的解法是用求解一般kSum的解法进行层层二分， 然后用Two Sum结合起来， 基本思路是这样， 实现细节还是比较复杂的， 即使是4Sum都比较复杂了， 所以面试中难度和实现细节也就到这了， kSum这种一般性的问题只需要知道思路就可以满足面试要求了哈。

LeetCode总结 -- 树的遍历篇

遍历树的数据结构中最常见的操作， 可以说大部分关于树的题目都是围绕遍历进行变体来解决的。 一般来说面试中遇到树的题目是用递归来解决的， 不过如果直接考察遍历， 那么一般递归的解法就过于简单了， 面试官一般还会问更多问题， 比如非递归实现， 或者空间复杂度分析以及能否优化等等。 树的遍历题目在LeetCode中有以下几个：
Binary Tree Inorder Traversal
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Zigzag Level Order Traversal

树的遍历基本上分成两种类型， 下面分别介绍：

第一种是以图的深度优先搜索为原型的遍历， 可以是中序， 先序和后序三种方式， 不过结点遍历的方式是相同的， 只是访问的时间点不同而已， 对应于Binary Tree Inorder Traversal， Binary Tree Preorder Traversal和Binary Tree Postorder Traversal这三道题目。
在这种类型中， 递归的实现方式是非常简单的， 只需要递归左右结点， 直到结点为空作为结束条件就可以， 哪种序就取决于你访问结点的时间。
不过一般这不能满足面试官的要求， 可能会接着问能不能用非递归实现一下， 这个说起来比较简单， 其实就是用一个栈手动模拟递归的过程， Binary Tree Inorder Traversal和Binary Tree Preorder Traversal比较简单， 用一个栈来保存前驱的分支结点（相当于图的深度搜索的栈）， 然后用一个结点来记录当前结点就可以了。 而Binary Tree Postorder Traversal则比较复杂一些， 保存栈和结点之后还得根据情况来判断当前应该走的方向（往左， 往右或者回溯）。 这里就不列举代码细节， 有兴趣的朋友可以看看具体题目的分析， 会更详细一些。
有时候非递归还是不能满足面试官， 还会问一问， 上面的做法时间和空间复杂度是多少。 我们知道， 正常遍历时间复杂度是O(n), 而空间复杂度是则是递归栈（或者自己维护的栈）的大小， 也就是O(logn)。 好了， 他会问能不能够在常量空间内解决树的遍历问题呢？ 确实还真可以， 这里就要介绍Morris Traversal的方法。 Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。 这样就节省了需要用栈来记录前驱或者后继结点的额外空间， 所以可以达到O（1）的空间复杂度。 不过这种方法有一个问题就是会暂时性的改动树的结构， 这在程序设计中并不是很好的习惯， 这些在面试中都可以和面试官讨论， 一般来说问到这里不会需要进行Morris遍历方法的代码实现了， 只需要知道这种方法和他的主要优劣势就可以了， 有兴趣知道实现的朋友可以看看具体题目的实现哈。

另一种是以图的广度优先搜索为原型的， 在树中称为层序遍历， LeetCode中有三种自顶向下层序， 自底向上层序和锯齿层序遍历， 对应于Binary Tree Level Order Traversal， Binary Tree Level Order Traversal II和Binary Tree Zigzag Level Order Traversal。
Binary Tree Level Order Traversal其实比较简单， 代码基本就是图的广度优先搜索， 思路就是维护一个队列存储上一层的结点， 逐层访问。 而Binary Tree Level Order Traversal II则要从最后一层倒序访问上来， 这个我没有想到太好的方法， 现在的实现就是把Binary Tree Level Order Traversal得到的层放入数据结构然后reverse过来， 确实没有太大的考核意义。 至于Binary Tree Zigzag Level Order Traversal因为每一层访问顺序有所改变， 而且是每次都反转顺序， 这让我们想到栈的数据结构， 所以这里不用队列对于上层结点进行， 而改用栈来保存， 就可以满足每层反转访问顺序的要求了。

树的遍历是一个老生常谈的题目， 不过仔细研究还是有一些考点的， 对于考查对数据结构和算法的理解还是不错的， 所以简单的东西也得重视哈。

LeetCode总结 -- 一维动态规划篇

这篇文章的主题是动态规划， 主要介绍LeetCode中一维动态规划的题目， 列表如下：
Climbing Stairs
Decode Ways
Unique Binary Search Trees
Maximum Subarray
Maximum Product Subarray
Best Time to Buy and Sell Stock

在介绍上述具体题目之前, 我们先说说动态规划的通常思路。 动态规划是一种算法思路（注意这里不要和递归混淆， 事实上递归和迭代只是两种不同的实现方法， 并不是算法）， 用一句话来总结就是， 动态规划是利用存储历史信息使得未来需要历史信息时不需要重新计 算， 从而达到降低时间复杂度， 用空间复杂度换取时间复杂度目的的方法。 我个人喜欢把动态规划分为以下几步：
1） 确定递推量。 这一步需要确定递推过程中要保留的历史信息数量和具体含义， 同时也会定下动态规划的维度；
2） 推导递推式。 根据确定的递推量， 得到如何利用存储的历史信息在有效时间（通常是常量或者线性时间）内得到当前的信息结果；
3） 计算初始条件。 有了递推式之后， 我们只需要计算初始条件， 就可以根据递推式得到我们想要的结果了。 通常初始条件都是比较简单的情况， 一般来说直接赋值即可；
4） （可选）考虑存储历史信息的空间维度。 这一步是基于对算法优化的考虑， 一般来说几维动态规划我们就用几维的存储空间是肯定可以实现的。 但是有时我们对于历史信息的要求不高， 比如这一步只需要用到上一步的历史信息， 而不需要更早的了， 那么我们可以只存储每一步的历史信息， 每步覆盖上一步的信息， 这样便可以少一维的存储空间， 从而优化算法的空间复杂度。
动态规划的时间复杂度是O(（维度）×（每步获取当前值所用的时间复杂度））。 基本上按照上面的思路， 动态规划的题目都可以解决， 不过最难的一般是在确定递推量， 一个好的递推量可以使得动态规划的时间复杂度尽量低。

接下来我们来看看具体题目， 一维动态规划的题目主要分成两类：

（1） 第一种是比较简单的， 直接地按照上面步骤就可以解出来的， 确定递归量， 然后按递归式迭代就可以得到。 这种类型的题目是： Climbing Stairs， Decode Ways和Unique Binary Search Trees。
Climbing Stairs中递推量很清晰， 就是爬到i级楼梯有多少种可行爬法。 而对于递推式我们可以看出， 要到达i级楼梯， 必须通过i－1级或者i－2级（以为只能爬一级或者两级）， 如此可以得到到达i级楼梯的方式有f（i）=f(i-1)+f(i-2)种， 这样递推式也就出来了。 而初始条件则是一级楼梯是一种解法， 两级楼梯是两种解法（2或者11）。 有了这些接下来递推到n级楼梯返回即可， 空间复杂度是O（n)(一维动态规划乘以每一步的常量操作）。 空间上我们发现每一步，只需要前两步的历史信息， 所以我们不需要存储所有历史信息， 只需要保存前两步， 然后迭代替换就可以了， 所以空间复杂度是O（2）=O（1）， 这里对应于上面的第四步。
Decode Ways中递推量也是类似的到达第i个字符可解析方式的数量， 递推式比Climbing Stairs稍微复杂一些， 要分情况讨论， 主要对于自己和前面一位组成数字的不同要分别处理一下， 这里就不列出来的，大家可以看看Decode Ways -- LeetCode。 虽然是分情况，不过每种情况也是可以常量时间更新信息的， 初始条件依然是非常简单的case， 空间上也是只需要保存前两步的信息， 所以时间和空间复杂度跟Climbing Stairs都是一样的。
Unique Binary Search Trees思路还是类似的， 递推式是稍有不同， 按左右子树划分然后进行累加， 最后归结为卡特兰数的模型。 这个问题仍然是一维动态规划， 但是求解单步信息时是一个线性操作， 所以时间复杂度是O（n^2)。 而空间上因为每一步都需要前面每一步的所有信息， 所以也无法优化， 是O(n)。

（2） 接下来我们介绍第二种类型， 虽然也是一维动态规划， 但是区别在于这类题目需要维护两个递推量， 所以思路上有一点技巧。 不过还是比较有通法的， 我通常把这种方法称为”局部最优和全局最优解法“。 这种方法中我们通常维护两个量， 一个是到目前为止最好的结果信息（全局最优）， 另一个必须包含新加进来的元素的最好的结果信息（局部最优）， 然后还是推导递推式， 计算初始条件， 跟动态规划的通常思路一样了。 Maximum Subarray和Best Time to Buy and Sell Stock就是这种类型的题目。
Maximum Subarray中对于递推量我们维护两个，一个是到目前为止最好的子数组， 而另一个量则是加入当前元素之后， 包含当前元素的最好的子数组， 最终我们是看全局最优的变量的最优值， 而局部最优却是我们在递推过程中维护全局最优所需要的。 递推式还是有点技巧， 第i+1步表达式如下：
  local[i+1]=Math.max(A[i], local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上 一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]；
  global[i+1]=Math(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。
初始条件都是0或者第一个元素既可以了， 一遍扫过来， 每次迭代更新两个量（都是常量时间）， 所以时间是O(n)。 空间上可以看出只需要上一步的信息， 所以只需要保存上一步的全局最优和局部最优即可， 复杂度是O（2）=O(1)。
Maximum Product Subarray的题目模型跟Maximum Subarray比较类似，只是把加法改成了乘法，思路还是用这个方法，只是注意这里两个负数相乘可能得到更优的乘法结果，所以我们在维护局部最优时把局部的最小值也存下来，这样遇到负数时就可以得到也许更大的乘积。其他就跟Maximum Subarray是一致的了。
Best Time to Buy and Sell Stock跟Maximum Subarray是完全一样的， 也是维护两个量， 一个是到目前为止最好的交易（全局最优）， 另一个是在当前一天卖出的最佳交易（局部最优）， 其他步骤也是一样的， 这里就不列出来了。

可以看出， 上面五道一维动态规划的题目都是按照我前面列出的四个步骤进行求解的， 事实上所有动态规划题目都是按照这个基本思路来的。 掌握了套路之后就是看对具体问题要维护的递推量的选择了，这个个人感觉还是比较靠经验的， 熟能生巧。

LeetCode总结 -- 二分查找篇

二分查找算法虽然简单，但面试中也比较常见，经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有：
Search Insert Position
Search for a Range
Sqrt(x)
Search a 2D Matrix
Search in Rotated Sorted Array
Search in Rotated Sorted Array II

这类题目基本可以分为如下四种题型：
1. Search Insert Position和Search for a Range是考察二分查找的基本用法。基本思路是每次取中间，如果等于目标即返回，否则根据大小关系切去一半，因此时间复杂度是O(logn)，空间复杂度O(1)。以Search Insert Position为例，其关键代码写法如下：

    int l = 0;
    int r = A.length-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(A[mid]==target)
            return mid;
        if(A[mid]<target)
            l = mid+1;
        else
            r = mid-1;
    }
    return l;

这样当循环停下来时，如果不是正好找到target，l指向的元素恰好大于target，r指向的元素恰好小于target，这里l和r可能越界，不过如果越界就说明大于（小于）target并且是最大（最小）。Search for a Range这道题能更好的解释这一点。其思路是先用二分查找找到其中一个target，然后再往左右找到target的边缘。我们主要看找边缘（往后找）的代码：

    int newL = m;
    int newR = A.length-1;
    while(newL<=newR)
    {
        int newM=(newL+newR)/2;
        if(A[newM]==target)
        {
            newL = newM+1;
        }
        else
        {
            newR = newM-1;
        }            
    }
    res[1]=newR;

我们的目标是在后面找到target的右边界，因为左边界已经等于target，所以判断条件是相等则向右看，大于则向左看，根据上面说的，循环停下来时，l指向的元素应该恰好大于target，r指向的元素应该等于target，所以此时的r正是我们想要的。向前找边缘也同理。

2. Sqrt(x)是数值处理的题目，但同时也可以用二分查找的思想来解决。因为我们知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。这里同样是考察二分查找的基本用法。代码如下：

public int sqrt(int x) {
    if(x<0) return -1;
    if(x==0) return 0;
    int l=1;
    int r=x/2+1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if(m<=x/m && x/(m+1)<m+1)
            return m;
        if(x/m<m)
        {
            r = m-1;
        }
        else
        {
            l = m+1;
        }
    }
    return 0;
}

这里要注意，这里判断相等的条件不是简单的 m == x/m, 而是 m<=x/m && x/(m+1)<m+1, 这是因为输出是整型，sqrt(14)=3 但 3 != 14/3. 所以我们需要一个范围框住结果。另外根据二分查找算法的特性，如果不能正好m==x/m停下，那么r指向的数字将正好是结果取整的值。所以我们也可以这样写：

public int sqrt(int x) {
    if(x<0) return -1;
    if(x==0) return 0;
    int l=1;
    int r=x/2+1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if(m==x/m )
            return m;
        if(x/m<m)
        {
            r = m-1;
        }
        else
        {
            l = m+1;
        }
    }
    return r;
}

3. Search a 2D Matrix是二分查找算法的多维应用，通过观察不难发现，输入的矩阵行内有序并且行间有序，所以查找只需要先按行查找，定位出在哪一行之后再进行列查找即可，两次二分查找，时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1)，这里不再赘述。

4. Search in Rotated Sorted Array和Search in Rotated Sorted Array II算是二分查找算法的一个变体。在Search in Rotated Sorted Array中，乍一看感觉数组已经不是有序的了，也就无法用二分查找算法，但仔细分析一下会发现，因为只rotate了一次，如果二分一下，总有一半是有序的，而且和另一半无区间重叠，我们只需要检查有序的一半的前后两个元素就可以确定target可能在哪一半。具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。

Search in Rotated Sorted Array II中array有重复元素，按照刚刚的思路，二分之后虽然一半是有序的，但我们会遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

总体来说，二分查找算法理解起来并不算难，但在实际面试的过程中可能会出现各种变体，如何灵活的运用才是制胜的关键。我们要抓住“有序”的特点，一旦发现输入有“有序”的特点，我们就可以考虑是否可以运用二分查找算法来解决该问题。

4Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/4sum/
这道题要求跟3Sum差不多，只是需求扩展到四个的数字的和了。我们还是可以按照3Sum中的解法，只是在外面套一层循环，相当于求n次3Sum。我们知道3Sum的时间复杂度是O(n^2)，所以如果这样解的总时间复杂度是O(n^3)。代码如下：

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null||num.length==0)
        return res;
    Arrays.sort(num);
    for(int i=num.length-1;i>2;i--)
    {
        if(i==num.length-1 || num[i]!=num[i+1])
        {
            ArrayList<ArrayList<Integer>> curRes = threeSum(num,i-1,target-num[i]);
            for(int j=0;j<curRes.size();j++)
            {
                curRes.get(j).add(num[i]);
            }
            res.addAll(curRes);
        }
    }
    return res;        
}
private ArrayList<ArrayList<Integer>> threeSum(int[] num, int end, int target)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    for(int i=end;i>1;i--)
    {
        if(i==end || num[i]!=num[i+1])
        {
            ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,target-num[i]);
            for(int j=0;j<curRes.size();j++)
            {
                curRes.get(j).add(num[i]);
            }
            res.addAll(curRes);
        }
    }
    return res;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int end, int target)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    int l=0;
    int r=end;
    while(l<r)
    {
        if(num[l]+num[r]==target)
        {
            ArrayList<Integer> item = new ArrayList<Integer>();
            item.add(num[l]);
            item.add(num[r]);
            res.add(item);
            l++;
            r--;
            while(l<r&&num[l]==num[l-1])
                l++;
            while(l<r&&num[r]==num[r+1])
                r--;
        }
        else if(num[l]+num[r]>target)
        {
            r--;
        }
        else
        {
            l++;
        }
    }
    return res;
}

上述这种方法比较直接，根据3Sum的结果很容易进行推广。那么时间复杂度能不能更好呢？其实我们可以考虑用二分法的思路，如果把所有的两两pair都求出来，然后再进行一次Two Sum的匹配，我们知道Two Sum是一个排序加上一个线性的操作，并且把所有pair的数量是O((n-1)+(n-2)+...+1)=O(n(n-1)/2)=O(n^2)。所以对O(n^2)的排序如果不用特殊线性排序算法是O(n^2*log(n^2))=O(n^2*2logn)=O(n^2*logn)，算法复杂度比上一个方法的O(n^3)是有提高的。
思路虽然明确，不过细节上会多很多情况要处理。首先，我们要对每一个pair建一个数据结构来存储元素的值和对应的index，这样做是为了后面当找到合适的两对pair相加能得到target值时看看他们是否有重叠的index，如果有说明它们不是合法的一个结果，因为不是四个不同的元素。接下来我们还得对这些pair进行排序，所以要给pair定义comparable的函数。最后，当进行Two Sum的匹配时因为pair不再是一个值，所以不能像Two Sum中那样直接跳过相同的，每一组都得进行查看，这样就会出现重复的情况，所以我们还得给每一个四个元素组成的tuple定义hashcode和相等函数，以便可以把当前求得的结果放在一个HashSet里面，这样得到新结果如果是重复的就不加入结果集了。
代码如下：

public class Node
{
    int index;
    int value;
    public Node(int index, int value)
    {
        this.index = index;
        this.value = value;
    }
}
public class Pair
{
    Node[] nodes;
    public Pair(Node n1, Node n2)
    {
        nodes = new Node[2];
        nodes[0] = n1;
        nodes[1] = n2;
    }
    public int getSum()
    {
        return nodes[0].value+nodes[1].value;
    }
}
public class Tuple
{
    ArrayList<Integer> num;
    public Tuple(ArrayList<Integer> num)
    {
        this.num = new ArrayList<Integer>(num);
        Collections.sort(this.num);
    }
    public int hashCode() {
        int hashcode = 5;
        for(int i=0;i<this.num.size();i++)
        {
            hashcode = 31*hashcode + this.num.get(i);
        }
        return hashcode;
    }
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (obj == this)
            return true;
        if (!(obj instanceof Tuple))
            return false;
        Tuple rhs = (Tuple) obj;
        for(int i=0;i<this.num.size();i++)
        {
            if(!this.num.get(i).equals(rhs.num.get(i)))
            {
                return false;
            }
        }            
        return true;
    }
}
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
    ArrayList<Pair> pairs = getPairs(num);
    Comparator<Pair> pairComparator = new Comparator<Pair>(){
        @Override
        public int compare(Pair p1, Pair p2){
            return p1.getSum()-p2.getSum();
        }
    };
    Collections.sort(pairs, pairComparator);
    return twoSum(pairs, target);
}
private ArrayList<Pair> getPairs(int[] num)
{
    ArrayList<Pair> res = new ArrayList<Pair>();
    for(int i=0;i<num.length-1;i++)
    {
        Node n1 = new Node(i,num[i]);
        for(int j=i+1;j<num.length;j++)
        {
            Node n2 = new Node(j,num[j]);
            Pair pair = new Pair(n1,n2);
            res.add(pair);
        }
    }
    return res;
}
private ArrayList<ArrayList<Integer>> twoSum(ArrayList<Pair> pairs, int target){
    HashSet<Tuple> hashSet = new HashSet<Tuple>();
    int l = 0;
    int r = pairs.size()-1;
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    while(l<r){
        if(pairs.get(l).getSum()+pairs.get(r).getSum()==target)
        {
            int lEnd = l;
            int rEnd = r;
            while(lEnd<rEnd && pairs.get(lEnd).getSum()==pairs.get(lEnd+1).getSum())
            {
                lEnd++;
            }
            while(lEnd<rEnd && pairs.get(rEnd).getSum()==pairs.get(rEnd-1).getSum())
            {
                rEnd--;
            }
            for(int i=l;i<=lEnd;i++)
            {
                for(int j=r;j>=rEnd;j--)
                {
                    if(check(pairs.get(i),pairs.get(j)))
                    {
                        ArrayList<Integer> item = new ArrayList<Integer>();
                        item.add(pairs.get(i).nodes[0].value);
                        item.add(pairs.get(i).nodes[1].value);
                        item.add(pairs.get(j).nodes[0].value);
                        item.add(pairs.get(j).nodes[1].value);
                        //Collections.sort(item);
                        Tuple tuple = new Tuple(item);
                        if(!hashSet.contains(tuple))
                        {
                            hashSet.add(tuple);
                            res.add(tuple.num);
                        }
                    }                        
                }
            }
            l = lEnd+1;
            r = rEnd-1;
        }
        else if(pairs.get(l).getSum()+pairs.get(r).getSum()>target)
        {
            r--;
        }
        else{
            l++;
        }
    }
    return res;
}
private boolean check(Pair p1, Pair p2)
{
    if(p1.nodes[0].index == p2.nodes[0].index || p1.nodes[0].index == p2.nodes[1].index)
        return false;
    if(p1.nodes[1].index == p2.nodes[0].index || p1.nodes[1].index == p2.nodes[1].index)
        return false;
    return true;
}

第二种方法比第一种方法时间上还是有提高的，其实这道题可以推广到k-Sum的问题，基本思想就是和第二种方法一样进行二分，然后两两结合，不过细节就非常复杂了（这点从上面的第二种解法就能看出来），所以不是很适合在面试中出现，有兴趣的朋友可以进一步思考或者搜索网上材料哈。

Unique Binary Search Trees II -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees-ii/
这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解，也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。代码如下：

public ArrayList<TreeNode> generateTrees(int n) {
    return helper(1,n);
}
private ArrayList<TreeNode> helper(int left, int right)
{
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    if(left>right)
    {
        res.add(null);
        return res;
    }
    for(int i=left;i<=right;i++)
    {
        ArrayList<TreeNode> leftList = helper(left,i-1);
        ArrayList<TreeNode> rightList = helper(i+1,right);
        for(int j=0;j<leftList.size();j++)
        {
            for(int k=0;k<rightList.size();k++)
            {
                TreeNode root = new TreeNode(i);
                root.left = leftList.get(j);
                root.right = rightList.get(k);
                res.add(root);
            }
        }
    }
    return res;
}

实现中还是有一些细节的，因为构造树时两边要遍历所有左右的匹配，然后接到根上面。
当然我们也可以像在Unique Binary Search Trees中那样存储所有的子树历史信息，然后进行拼合，虽然可以省一些时间，但是最终还是逃不过每个结果要一次运算，时间复杂度还是非多项式的，并且要耗费大量的空间，感觉这样的意义就不是很大了。

Unique Binary Search Trees -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees/
这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：

熟悉卡特兰数的朋友可能已经发现了，这正是卡特兰数的一种定义方式，是一个典型的动态规划的定义方式（根据其实条件和递推式求解结果）。所以思路也很明确了，维护量res[i]表示含有i个结点的二叉查找树的数量。根据上述递推式依次求出1到n的的结果即可。
时间上每次求解i个结点的二叉查找树数量的需要一个i步的循环，总体要求n次，所以总时间复杂度是O(1+2+...+n)=O(n^2)。空间上需要一个数组来维护，并且需要前i个的所有信息，所以是O(n)。代码如下：

public int numTrees(int n) {
    if(n<=0)
        return 0;
    int[] res = new int[n+1];
    res[0] = 1;
    res[1] = 1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            res[i] += res[j]*res[i-j-1];
        }
    }
    return res[n];
}

这种求数量的题目一般都容易想到用动态规划的解法，这道题的模型正好是卡特兰数的定义。当然这道题还可以用卡特兰数的通项公式来求解，这样时间复杂度就可以降低到O(n)。因为比较直接，这里就不列举代码了。
如果是求解所有满足要求的二叉树（而不仅仅是数量）那么时间复杂度是就取决于结果的数量了，不再是一个多项式的解法了，有兴趣的朋友可以看看Unique Binary Search Trees II。

Restore IP Addresses -- LeetCode

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/
这道题的解法非常接近于NP问题，也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。这里除了上述的结束条件外，另一个就是字符串读完了。可以看出这棵树的规模是固定的，不会像平常的NP问题那样，时间复杂度取决于输入的规模，是指数量级的，所以这道题并不是NP问题，因为他的分支是四段，有限制。代码如下：

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> res = new ArrayList<String>();
    if(s==null || s.length()==0)
        return res;
    helper(s,0,1,"",res);
    return res;
}
private void helper(String s, int index, int segment, String item, ArrayList<String> res)
{
    if(index>=s.length())
        return;
    if(segment == 4)
    {
        String str = s.substring(index);
        if(isValid(str))
        {
            res.add(item+"."+str);
        }
        return;
    }
    for(int i=1;i<4&&(i+index<=s.length());i++)
    {
        String str = s.substring(index, index+i);
        if(isValid(str))
        {
            if(segment==1)
                helper(s,index+i,segment+1,str,res);
            else
                helper(s,index+i,segment+1,item+"."+str,res);
        }
    }
}
private boolean isValid(String str)
{
    if(str==null || str.length()>3)
        return false;
    int num = Integer.parseInt(str);
    if(str.charAt(0)=='0' && str.length()>1)
        return false;
    if(num>=0 && num<=255)
        return true;
    return false;
}

实现中需要一个判断数字是否为合法ip地址的一项的函数，首先要在0-255之间，其次前面字符不能是0。剩下的就是NP问题的套路了，递归中套一个for循环，不熟悉的朋友可以看看N-Queens哈。

Interleaving String -- LeetCode

原题链接: http://oj.leetcode.com/problems/interleaving-string/
这是一道关于字符串操作的题目，要求是判断一个字符串能不能由两个字符串按照他们自己的顺序，每次挑取两个串中的一个字符来构造出来。
像这种判断能否按照某种规则来完成求是否或者某个量的题目，很容易会想到用动态规划来实现。
先说说维护量，res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出s3的前i+j个字符，如此最后结果就是res[s1.length()][s2.length()]，判断是否为真即可。接下来就是递推式了，假设知道res[i][j]之前的所有历史信息，我们怎么得到res[i][j]。可以看出，其实只有两种方式来递推，一种是选取s1的字符作为s3新加进来的字符，另一种是选s2的字符作为新进字符。而要看看能不能选取，就是判断s1(s2)的第i(j)个字符是否与s3的i+j个字符相等。如果可以选取并且对应的res[i-1][j](res[i][j-1])也为真，就说明s3的i+j个字符可以被表示。这两种情况只要有一种成立，就说明res[i][j]为真，是一个或的关系。所以递推式可以表示成

res[i][j] = res[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)

时间上因为是一个二维动态规划，所以复杂度是O(m*n)，m和n分别是s1和s2的长度。最后就是空间花费，可以看出递推式中只需要用到上一行的信息，所以我们只需要一个一维数组就可以完成历史信息的维护，为了更加优化，我们把短的字符串放在内层循环，这样就可以只需要短字符串的长度即可，所以复杂度是O(min(m,n))。代码如下：

public boolean isInterleave(String s1, String s2, String s3) {
    if(s1.length()+s2.length()!=s3.length())
        return false;
    String minWord = s1.length()>s2.length()?s2:s1;
    String maxWord = s1.length()>s2.length()?s1:s2;
    boolean[] res = new boolean[minWord.length()+1];
    res[0] = true;
    for(int i=0;i<minWord.length();i++)
    {
        res[i+1] = res[i] && minWord.charAt(i)==s3.charAt(i);
    }
    for(int i=0;i<maxWord.length();i++)
    {
        res[0] = res[0] && maxWord.charAt(i)==s3.charAt(i);
        for(int j=0;j<minWord.length();j++)
        {
            res[j+1] = res[j+1]&&maxWord.charAt(i)==s3.charAt(i+j+1) || res[j]&&minWord.charAt(j)==s3.charAt(i+j+1);
        }
    }
    return res[minWord.length()];
}

动态规划其实还是有套路的，无非就是找到维护量，然后得到递推式，接下来看看历史信息对于空间的需求，尽量优化，会在后面对于动态规划做一个比较通用的总结哈。

Reverse Linked List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-linked-list-ii/
这道题是比较常见的链表反转操作，不过不是反转整个链表，而是从m到n的一部分。分为两个步骤，第一步是找到m结点所在位置，第二步就是进行反转直到n结点。反转的方法就是每读到一个结点，把它插入到m结点前面位置，然后m结点接到读到结点的下一个。总共只需要一次扫描，所以时间是O(n)，只需要几个辅助指针，空间是O(1)。代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null)
        return null;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode preNode = dummy;
    int i=1;
    while(preNode.next!=null && i<m)
    {
        preNode = preNode.next;
        i++;
    }
    if(i<m)
        return head;
    ListNode mNode = preNode.next;
    ListNode cur = mNode.next;
    while(cur!=null && i<n)
    {
        ListNode next = cur.next;
        cur.next = preNode.next;
        preNode.next = cur;
        mNode.next = next;
        cur = next;
        i++;
    }
    return dummy.next;
}

上面的代码还是有些细节的，链表的题目就是这样，想起来道理很简单，实现中可能会出些小差错，还是熟能生巧哈。

Subsets II -- LeetCode

原题链接: http://oj.leetcode.com/problems/subsets-ii/
这道题跟Subsets一样是经典的NP问题--求子集。比Subsets稍微复杂一些的是这里的集合中可能出现重复元素，因此我们在求子集的时候要避免出现重复的子集。在Subsets中我们每次加进一个元素就会把原来的子集都加上这个元素，然后再加入到结果集中，但是这样重复的元素就会产生重复的子集。为了避免这样的重复，需要用个小技巧。
其实比较简单，就是每当遇到重复元素的时候我们就只把当前结果集的后半部分加上当前元素加入到结果集中，因为后半部分就是上一步中加入这个元素的所有子集，上一步这个元素已经加入过了，前半部分如果再加就会出现重复。所以算法上复杂度上没有提高，反而少了一些操作，就是遇到重复时少做一半，不过这里要对元素集合先排序，否则不好判断重复元素。同样的还是可以用递归和非递归来解，不过对于重复元素的处理是一样的。递归的代码如下：

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    if(num == null)
        return null;
    Arrays.sort(num);
    ArrayList<Integer> lastSize = new ArrayList<Integer>();
    lastSize.add(0);
    return helper(num, num.length-1, lastSize);
}
private ArrayList<ArrayList<Integer>> helper(int[] num, int index, ArrayList<Integer> lastSize)
{
    if(index == -1)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> elem = new ArrayList<Integer>();
        res.add(elem);
        return res;
    }
    ArrayList<ArrayList<Integer>> res = helper(num,index-1,lastSize);
    int size = res.size();
    int start = 0;
    if(index>0 && num[index]==num[index-1])
        start = lastSize.get(0);
    for(int i=start;i<size;i++)
    {
        ArrayList<Integer> elem = new ArrayList<Integer>(res.get(i));
        elem.add(num[index]);
        res.add(elem);
    }
    lastSize.set(0,size);
    return res;
}

非递归的代码如下：

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    res.add(new ArrayList<Integer>());
    if(num==null || num.length==0)
        return res;
    Arrays.sort(num);
    int start = 0;
    for(int i=0;i<num.length;i++)
    {
        int size = res.size();
        for(int j=start;j<size;j++)
        {
            ArrayList<Integer> newItem = new ArrayList<Integer>(res.get(j));
            newItem.add(num[i]);
            res.add(newItem);
        }
        if(i<num.length-1 && num[i]==num[i+1])
        {
            start = size;
        }
        else
        {
            start = 0;
        }
    }
    return res;
}

这种NP问题的重复处理在LeetCode有一定出现频率，比如还有Permutations II也是这样的，其实本质就是当一个重复元素进来时忽略上一个元素已经有的结果，只考虑由重复元素所产生的新结果。

Decode Ways -- LeetCode

原题链接: http://oj.leetcode.com/problems/decode-ways/
这道题要求解一个数字串按照字符串编码方式可解析方式的数量。看到这种求数量的，我们很容易想到动态规划来存储前面信息，然后迭代得到最后结果。
我们维护的量res[i]是表示前i个数字有多少种解析的方式，接下来来想想递归式，有两种方式：第一种新加进来的数字不然就是自己比较表示一个字符，那么解析的方式有res[i-1]种，第二种就是新加进来的数字和前一个数字凑成一个字符，解析的方式有res[i-2]种（因为上一个字符和自己凑成了一个）。当然这里要判断前面说的两种情况能否凑成一个字符，也就是范围的判断，如果可以才有对应的解析方式，如果不行，那么就是0。最终结果就是把这两种情况对应的解析方式相加。这里可以把范围分成几个区间：
（1）00：res[i]=0（无法解析，没有可行解析方式）；
（2）10, 20：res[i]=res[i-2]（只有第二种情况成立）；
（3）11-19, 21-26：res[i]=res[i-1]+res[i-2]（两种情况都可行）；
（4）01-09, 27-99：res[i]=res[i-1]（只有第一种情况可行）；
递推式就是按照上面的规则来得到，接下来我们只要进行一遍扫描，然后依次得到维护量就可以了，算法的时间复杂度是O(n)。空间上可以看出我们每次只需要前两位的历史信息，所以只需要维护三个变量然后迭代赋值就可以了，所以空间复杂度是O(1)。代码如下：

public int numDecodings(String s) {
    if(s==null || s.length()==0 || s.charAt(0)=='0')
    {
        return 0;
    }
    int num1=1;
    int num2=1;
    int num3=1;
    for(int i=1;i<s.length();i++)
    {
        if(s.charAt(i)=='0')
        {
            if(s.charAt(i-1)=='1' || s.charAt(i-1)=='2')
                num3 = num1;
            else
                return 0;
        }
        else
        {
            if(s.charAt(i-1)=='0' || s.charAt(i-1)>='3')
                num3 = num2;
            else
            {
                if(s.charAt(i-1)=='2' && s.charAt(i)>='7' && s.charAt(i)<='9')
                    num3 = num2;
                else
                    num3 = num1+num2;
            }
        }
        num1 = num2;
        num2 = num3;
    }
    return num2;
}

这道题是一维动态规划的题目，递推式关系来说是比较容易得到的，主要是要对这些两位数进行划分有一些细节，容易出小错误。

Recover Binary Search Tree -- LeetCode

原题链接: http://oj.leetcode.com/problems/recover-binary-search-tree/
这道题是要求恢复一颗有两个元素调换错了的二叉查找树。一开始拿到可能会觉得比较复杂，其实观察出规律了就比较简单。主要还是利用二叉查找树的主要性质，就是中序遍历是有序的性质。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢？有两种情况，如果是中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；如果是不相邻的两个元素被调换了，举个例子很容易可以发现，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。比如1234567,1和5调换了，会得到5234167，逆序发生在52和41，我们需要把4和1调过来，那么就是52的第一个元素，41的第二个元素调换即可。
搞清楚了规律就容易实现了，中序遍历寻找逆序情况，调换的第一个元素，永远是第一个逆序的第一个元素，而调换的第二个元素如果只有一次逆序，则是那一次的后一个，如果有两次逆序则是第二次的后一个。算法只需要一次中序遍历，所以时间复杂度是O(n)，空间是栈大小O(logn)。代码如下：

public void recoverTree(TreeNode root) {
    if(root == null)
        return;
    ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
    pre.add(null);
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    helper(root,pre, res);
    if(res.size()>0)
    {
        int temp = res.get(0).val;
        res.get(0).val = res.get(1).val;
        res.get(1).val = temp;
    }
}
private void helper(TreeNode root, ArrayList<TreeNode> pre, ArrayList<TreeNode> res)
{
    if(root == null)
    {
        return;
    }
    helper(root.left, pre, res);
    if(pre.get(0)!=null && pre.get(0).val>root.val)
    {
        if(res.size()==0)
        {
            res.add(pre.get(0));
            res.add(root);
        }
        else
        {
            res.set(1,root);
        }
    }
    pre.set(0,root);
    helper(root.right,pre,res);
}

可以看到实现中pre用了一个ArrayList来存，这样做的原因是因为java都是值传递，所以我们要全局变化pre的值（而不是在当前函数里），只能传一个数组，才能改变结点的地址，这一点非常重要，也是java和C++一个比较大的区别，不了解的朋友可以研究一下哈。
这道题还是考察二叉树遍历，不过应用题目要求套了一个不同的外壳，需要我们利用二叉查找树的性质观察出规律之后才能求解。

Gray Code -- LeetCode

原题链接: http://oj.leetcode.com/problems/gray-code/
这道题要求求出n位的格雷码对应的二进制数，主要在于找到一种格雷码的递增方法（gray code并不是唯一的，可以有多种）。
我们来看看有了n-1位的格雷码如何得到n位的格雷码呢？其实方法比较简单，首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码，它们一定是合法的因为除了第一位（都是0）其余位都跟n-1的格雷码一致，所以两两之间只相差一位，满足要求。接下来看看如何接上剩下的2^(n-1)个，我们把n-1位的格雷码倒序排列，然后在每个前面添加1，然后接到上述的前2^(n-1)个就可以了。首先因为是倒序过来，所以中间两个元素除去第一位其他都是一样的（因为原来最后一个，现在倒序过来就是第一个），而他们第一位分别是0和1，满足格雷码的要求。而剩下的元素因为我们是n-1位的格雷码倒序排列，所以两两都是满足要求的，加上前面都一样的位1，仍然满足条件。最后看看这些数字是不是都不一样，前半部分和后半部分肯定不会一样，而因为前半部分都是0开头，后半部分都是1打头，所以互相之间也不会有重复，可以看出覆盖了所有数字，而且依次下来均满足条件。
如此我们提出了格雷码的递推方法，我们只需要做一次位数的循环，每次根据上面结果构造当前位数的结果即可。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。代码如下：

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(n<0)
        return res;
    if(n==0)
    {
        res.add(0);
        return res;
    }
    res.add(0);
    res.add(1);
    for(int i=2;i<=n;i++)
    {
        int size = res.size();
        for(int j=size-1;j>=0;j--)
        {
            res.add(res.get(j)+(1<<(i-1)));
        }
    }
    return res;
}

可以看出上面代码并不需要处理前半部分，因为要求的是二进制数对应的整数，所以在前面加0等于原来的数字，所以前面数字只需要保持原来就行，后面进行倒序然后对最高位赋1即可。感觉更接近于一道寻找规律的题目，实现上用到一点位运算会比较简单，不过位运算是这道题的考察点之一，面试中还是有关于位运算的题目，需要熟悉一下哈。

Binary Tree Zigzag Level Order Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
这道题其实还是树的层序遍历Binary Tree Level Order Traversal，如果不熟悉的朋友可以先看看哈。不过这里稍微做了一点变体，就是在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以会同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。代码如下：

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(root==null)
        return res;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    int level=1;
    ArrayList<Integer> item = new ArrayList<Integer>();
    item.add(root.val);
    res.add(item);
    stack.push(root);
    while(!stack.isEmpty())
    {
        LinkedList<TreeNode> newStack = new LinkedList<TreeNode>();
        item = new ArrayList<Integer>();
        while(!stack.isEmpty())
        {
            TreeNode node = stack.pop();
            if(level%2==0)
            {
                if(node.left!=null)
                {
                    newStack.push(node.left);
                    item.add(node.left.val);
                }
                if(node.right!=null)
                {
                    newStack.push(node.right);
                    item.add(node.right.val);
                }
            }
            else
            {
                if(node.right!=null)
                {
                    newStack.push(node.right);
                    item.add(node.right.val);
                }
                if(node.left!=null)
                {
                    newStack.push(node.left);
                    item.add(node.left.val);
                }                   
            }
        }
        level++;
        if(item.size()>0)
            res.add(item);
        stack = newStack;
    }
    return res;
}

上面的算法其实还是一次广度优先搜索，只是在读取每一层结点交替的交换顺序。毕竟面试中像Binary Tree Level Order Traversal有时候考得太多了，面试官会觉得你肯定练过，所以会稍作变体，来考察对于编程和算法的基本理解。

Scramble String -- LeetCode

原题链接: http://oj.leetcode.com/problems/scramble-string/
这道题看起来是比较复杂的，如果用brute force，每次做切割，然后递归求解，是一个非多项式的复杂度，一般来说这不是面试官想要的答案。
这其实是一道三维动态规划的题目，我们提出维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。
有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]。判断这个是不是满足，其实我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的，因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。
上面说的是劈一刀的情况，对于s1[i...i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立，那么两个串就是scramble的。
总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k<len，也就是对于所有len-1种劈法的结果求或运算。因为信息都是计算过的，对于每种劈法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种劈法）。
如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大有事的，空间复杂度是O(n^3)。代码如下：

public boolean isScramble(String s1, String s2) {
    if(s1==null || s2==null || s1.length()!=s2.length())
        return false;
    if(s1.length()==0)
        return true;
    boolean[][][] res = new boolean[s1.length()][s2.length()][s1.length()+1];
    for(int i=0;i<s1.length();i++)
    {
        for(int j=0;j<s2.length();j++)
        {
            res[i][j][1] = s1.charAt(i)==s2.charAt(j);
        }
    }
    for(int len=2;len<=s1.length();len++)
    {
        for(int i=0;i<s1.length()-len+1;i++)
        {
            for(int j=0;j<s2.length()-len+1;j++)
            {
                for(int k=1;k<len;k++)
                {
                    res[i][j][len] |= res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k];
                }
            }
        }
    }
    return res[0][0][s1.length()];
}

个人觉得这是LeetCode中最难的动态规划的题目了，要进行一次三维动态规划，对于维护量的含义也比较讲究。有朋友会讨论这个维护量是怎么提出来的，我自己也没什么绝对的方法，还是熟能生巧，靠“感觉”，做的题目多了就自然来了，这个做高中数学题有点类似哈，辅助线是靠“灵感”的哈。面试中如果遇到就是top难度的了，不过即使如此，只要思路清晰，还是可以记住的。如果没做过，个人觉得比较难当场想出来，不过算法大牛就另说了，这种题很经常出现在编程比赛中，ACM高手还是不在话下的哈。

Partition List -- LeetCode

原题链接: http://oj.leetcode.com/problems/partition-list/
这是一道链表操作的题目，要求把小于x的元素按顺序放到链表前面。我们仍然是使用链表最常用的双指针大法，一个指向当前小于x的最后一个元素，一个进行往前扫描。如果元素大于x，那么继续前进，否则，要把元素移到前面，并更新第一个指针。这里有一个小细节，就是如果不需要移动（也就是已经是接在小于x的最后元素的后面了），那么只需要继续前进即可。算法时间复杂度是O(n)，空间只需要几个辅助变量，是O(1)。代码如下：

public ListNode partition(ListNode head, int x) {
    if(head == null)
        return null;
    ListNode helper = new ListNode(0);
    helper.next = head;
    ListNode walker = helper;
    ListNode runner = helper;
    while(runner.next!=null)
    {
        if(runner.next.val<x)
        {
            if(walker!=runner)
            {
                ListNode next = runner.next.next;
                runner.next.next = walker.next;
                walker.next = runner.next;
                runner.next = next;
            }
            else
                runner = runner.next;
            walker = walker.next;
        }
        else
        {
            runner = runner.next;
        }
    }
    return helper.next;
}

这道题思路比较清晰，不过还是有点细节的，第一次写可能不容易完全写对，可以练习练习。

Maximal Rectangle -- LeetCode

原题链接: http://oj.leetcode.com/problems/maximal-rectangle/
这是一道非常综合的题目，要求在0-1矩阵中找出面积最大的全1矩阵。刚看到这道题会比较无从下手，brute force就是对于每个矩阵都看一下，总共有m(m+1)/2*n(n+1)/2个子矩阵（原理跟字符串子串类似，字符串的子串数有n(n+1)/2，只是这里是二维情形，所以是两个相乘），复杂度相当高，肯定不是面试官想要的答案，就不继续想下去了。
这道题的解法灵感来自于Largest Rectangle in Histogram这道题，假设我们把矩阵沿着某一行切下来，然后把切的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。
算法的基本思路已经出来了，剩下的就是一些节省时间空间的问题了。
我们如何计算某一行为底面时直方图的高度呢？ 如果重新计算，那么每次需要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹，如果我们知道上一行直方图的高度，我们只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。利用历史信息，我们就可以在线行时间内完成对高度的更新。我们知道，Largest Rectangle in Histogram的算法复杂度是O(n)。所以完成对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次，那么算法总时间复杂度是O(m*n)。
空间上，我们只需要保存上一行直方图的高度O(n)，加上Largest Rectangle in Histogram中所使用的空间O(n)，所以总空间复杂度还是O(n)。代码如下：

public int maximalRectangle(char[][] matrix) {
    if(matrix==null || matrix.length==0 || matrix[0].length==0)
    {
        return 0;
    }
    int maxArea = 0;
    int[] height = new int[matrix[0].length];
    for(int i=0;i<matrix.length;i++)
    {
        for(int j=0;j<matrix[0].length;j++)
        {
            height[j] = matrix[i][j]=='0'?0:height[j]+1;
        }
        maxArea = Math.max(largestRectangleArea(height),maxArea);
    }
    return maxArea;
}
public int largestRectangleArea(int[] height) {
    if(height==null || height.length==0)
    {
        return 0;
    }
    int maxArea = 0;
    LinkedList<Integer> stack = new LinkedList<Integer>();
    for(int i=0;i<height.length;i++)
    {
        
        while(!stack.isEmpty() && height[i]<=height[stack.peek()])
        {
            int index = stack.pop();
            int curArea = stack.isEmpty()?i*height[index]:(i-stack.peek()-1)*height[index];
            maxArea = Math.max(maxArea,curArea);
        }
        stack.push(i);
    }
    while(!stack.isEmpty())
    {
        int index = stack.pop();
        int curArea = stack.isEmpty()?height.length*height[index]:(height.length-stack.peek()-1)*height[index];
        maxArea = Math.max(maxArea,curArea);            
    }
    return maxArea;
}

这道题最后的复杂度是非常令人满意的，居然在O(m*n)时间内就可以完成对最大矩阵的搜索，可以看出这已经是下界（因为每个元素总要访问一下才知道是不是1）了。难度还是比较大的，相信要在面试当场想到这种方法是很不容易的。个人很喜欢这道题，既用到了别的题目，又有动态规划的思想，复杂度还非常漂亮，又一次体现了算法的魅力哈。

Construct Binary Tree from Inorder and Postorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
这道题和Construct Binary Tree from Preorder and Inorder Traversal思路完全一样，如果有朋友不了解，请先看看Construct Binary Tree from Preorder and Inorder Traversal哈。这里的区别是要从中序遍历和后序遍历中构造出树，算法还是一样，只是现在取根是从后面取（因为后序遍历根是遍历的最后一个元素）。思想和代码基本都是差不多的，自然时间复杂度和空间复杂度也还是O(n)。代码如下：

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder==null || postorder==null || inorder.length==0 || postorder.length==0)
    {
        return null;
    }
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0;i<inorder.length;i++)
    {
        map.put(inorder[i],i);
    }
    return helper(inorder,postorder,0,inorder.length-1, 0, postorder.length-1,map);
}
private TreeNode helper(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR, HashMap<Integer, Integer> map)
{
    if(inL>inR || postL>postR)
        return null;
    TreeNode root = new TreeNode(postorder[postR]);
    int index = map.get(root.val);
    root.left = helper(inorder,postorder,inL,index-1,postL,postL+index-inL-1,map);
    root.right = helper(inorder,postorder,index+1,inR,postR-(inR-index),postR-1,map);
    return root;
}

这道题和Construct Binary Tree from Preorder and Inorder Traversal是树中难度比较大的题目了，有朋友可能会想根据先序遍历和后序遍历能不能重新构造出树来，答案是否定的。只有中序便利可以根据根的位置切开左右子树，其他两种遍历都不能做到，其实先序遍历和后序遍历是不能唯一确定一棵树的，会有歧义发生，也就是两棵不同的树可以有相同的先序遍历和后序遍历，有兴趣的朋友可以试试举出这种例子哈。

Construct Binary Tree from Preorder and Inorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
这道题是树中比较有难度的题目，需要根据先序遍历和中序遍历来构造出树来。这道题看似毫无头绪，其实梳理一下还是有章可循的。下面我们就用一个例子来解释如何构造出树。
假设树的先序遍历是12453687，中序遍历是42516837。这里最重要的一点就是先序遍历可以提供根的所在，而根据中序遍历的性质知道根的所在就可以将序列分为左右子树。比如上述例子，我们知道1是根，所以根据中序遍历的结果425是左子树，而6837就是右子树。接下来根据切出来的左右子树的长度又可以在先序便利中确定左右子树对应的子序列（先序遍历也是先左子树后右子树）。根据这个流程，左子树的先序遍历和中序遍历分别是245和425，右子树的先序遍历和中序遍历则是3687和6837，我们重复以上方法，可以继续找到根和左右子树，直到剩下一个元素。可以看出这是一个比较明显的递归过程，对于寻找根所对应的下标，我们可以先建立一个HashMap，以免后面需要进行线行搜索，这样每次递归中就只需要常量操作就可以完成对根的确定和左右子树的分割。
算法最终相当于一次树的遍历，每个结点只会被访问一次，所以时间复杂度是O(n)。而空间我们需要建立一个map来存储元素到下标的映射，所以是O(n)。代码如下：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder==null || inorder==null)
        return null;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0;i<inorder.length;i++)
    {
        map.put(inorder[i],i);
    }
    return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1, map);
}
private TreeNode helper(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR, HashMap<Integer, Integer> map)
{
    if(preL>preR || inL>inR)
        return null;
    TreeNode root = new TreeNode(preorder[preL]);
    int index = map.get(root.val);
    root.left = helper(preorder, preL+1, index-inL+preL, inorder, inL, index-1, map);
    root.right = helper(preorder, preL+index-inL+1, preR, inorder, index+1, inR,map);
    return root;
}

可以看出上面实现结果还是非常接近于一次树的遍历的，只是我们是以一个构造树的形式，在遍历中把树创建出来。这种题目算是树中的难题了，不过理清思路，其实也不过如此哈~

Remove Duplicates from Sorted List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
这道题跟Remove Duplicates from Sorted List比较类似，只是这里要把出现重复的元素全部删除。其实道理还是一样，只是现在要把前驱指针指向上一个不重复的元素中，如果找到不重复元素，则把前驱指针知道该元素，否则删除此元素。算法只需要一遍扫描，时间复杂度是O(n)，空间只需要几个辅助指针，是O(1)。代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if(head == null)
        return head;
    ListNode helper = new ListNode(0);
    helper.next = head;
    ListNode pre = helper;
    ListNode cur = head;
    while(cur!=null)
    {
        while(cur.next!=null && pre.next.val==cur.next.val)
        {
            cur = cur.next;
        }
        if(pre.next==cur)
        {
            pre = pre.next;
        }
        else
        {
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    
    return helper.next;
}

可以看到，上述代码中我们创建了一个辅助的头指针，是为了修改链表头的方便。前面介绍过，一般会改到链表头的题目就会需要一个辅助指针，是比较常见的技巧。

Remove Duplicates from Sorted List -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/
这是一道比较简单的链表操作的题目，要求是删去有序链表中重复的元素。方法比较清晰，维护两个指针，一个指向当前不重复的最后一个元素，一个进行依次扫描，遇到不重复的则更新第一个指针，继续扫描，否则就把前面指针指向当前元素的下一个（即把当前元素从链表中删除）。时间上只需要一次扫描，所以是O(n)，空间上两个额外指针，是O(1)。代码如下：

public ListNode deleteDuplicates(ListNode head) {
    if(head == null)
        return head;
    ListNode pre = head;
    ListNode cur = head.next;
    while(cur!=null)
    {
        if(cur.val == pre.val)
            pre.next = cur.next;
        else    
            pre = cur;
        cur = cur.next;
    }
    return head;
}

链表操作在LeetCode中占有一定的比例，不过面试中出现的频率并不是特别高，不过基本的操作还是要熟练的。这道题目还可以求于另一个数据结构数组中，也比较简单，有兴趣可以看看Remove Duplicates from Sorted Array。

Remove Duplicates from Sorted Array II -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
这道题跟Remove Duplicates from Sorted Array比较类似，区别只是这里元素可以重复出现至多两次，而不是一次。其实也比较简单，只需要维护一个counter，当counter是2时，就直接跳过即可，否则说明元素出现次数没有超，继续放入结果数组，若遇到新元素则重置counter。总体算法只需要扫描一次数组，所以时间上是O(n)，空间上只需要维护一个index和counter，所以是O(1)。代码如下：

public int removeDuplicates(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int idx = 0;
    int count = 0;
    for(int i=0;i<A.length;i++)
    {
        if(i>0 && A[i]==A[i-1])
        {
            count++;
            if(count>=3)
                continue;
        }
        else
        {
            count = 1;
        }
        A[idx++]=A[i];
    }
    return idx;
}

这种简单数组操作的问题在电面中比较常见，既然简单，所以出手就要稳，不能出错，还是要保证无误哈。

Word Search -- LeetCode

原题链接: http://oj.leetcode.com/problems/word-search/
这道题很容易感觉出来是图的题目，其实本质上还是做深度优先搜索。基本思路就是从某一个元素出发，往上下左右深度搜索是否有相等于word的字符串。这里注意每次从一个元素出发时要重置访问标记（也就是说虽然单次搜索字符不能重复使用，但是每次从一个新的元素出发，字符还是重新可以用的）。深度优先搜索的算法就不再重复解释了，不了解的朋友可以看看wiki - 深度优先搜索。我们知道一次搜索的复杂度是O(E+V)，E是边的数量，V是顶点数量，在这个问题中他们都是O(m*n)量级的（因为一个顶点有固定上下左右四条边）。加上我们对每个顶点都要做一次搜索，所以总的时间复杂度最坏是O(m^2*n^2)，空间上就是要用一个数组来记录访问情况，所以是O(m*n)。代码如下：

public boolean exist(char[][] board, String word) {
    if(word==null || word.length()==0)
        return true;
    if(board==null || board.length==0 || board[0].length==0)
        return false;
    boolean[][] used = new boolean[board.length][board[0].length];
    for(int i=0;i<board.length;i++)
    {
        for(int j=0;j<board[0].length;j++)
        {
            if(search(board,word,0,i,j,used))
                return true;
        }
    }
    return false;
}
private boolean search(char[][] board, String word, int index, int i, int j, boolean[][] used)
{
    if(index == word.length())
        return true;
    if(i<0 || j<0 || i>=board.length || j>=board[0].length || used[i][j] || board[i][j]!=word.charAt(index))
        return false;
    used[i][j] = true;
    boolean res = search(board,word,index+1,i-1,j,used) || search(board,word,index+1,i+1,j,used)
        || search(board,word,index+1,i,j-1,used) || search(board,word,index+1,i,j+1,used);
    used[i][j] = false;
    return res;
}

这道题其实还可以变一变，比如字符可以重复使用。准备的时候多联想还是比较好的，因为面试中常常会做完一道题会变一下问问，虽然经常不用重新写代码，但是想了解一下思路，有兴趣的朋友可以想想哈。

Subsets -- LeetCode

原题链接: http://oj.leetcode.com/problems/subsets/
求子集问题是经典的NP问题，复杂度上我们就无法强求了哈，肯定是非多项式量级的。一般来说这个问题有两种解法：递归和非递归。
我们先来说说递归解法，主要递推关系就是假设函数返回递归集合，现在加入一个新的数字，我们如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集，然后放入原有集合中（原来的集合中的元素不用删除，因为他们也是合法子集）。而结束条件就是如果没有元素就返回空集（注意空集不是null，而是没有元素的数组）就可以了。时间和空间都是取决于结果的数量，也就是O(2^n)，代码如下：

public ArrayList<ArrayList<Integer>> subsets(int[] num) {
    if(num == null)
        return null;
    Arrays.sort(num);
    return helper(num, num.length-1);
}
private ArrayList<ArrayList<Integer>> helper(int[] num, int index)
{
    if(index == -1)
    {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> elem = new ArrayList<Integer>();
        res.add(elem);
        return res;
    }
    ArrayList<ArrayList<Integer>> res = helper(num,index-1);
    int size = res.size();
    for(int i=0;i<size;i++)
    {
        ArrayList<Integer> elem = new ArrayList<Integer>(res.get(i));
        elem.add(num[index]);
        res.add(elem);
    }
    return res;
}

其实非递归解法的思路和递归是一样的，只是没有回溯过程，也就是自无到有的一个个元素加进来，然后构造新的子集加入结果集中，代码如下：

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
     ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
     res.add(new ArrayList<Integer>());
     if(S == null || S.length == 0)
        return res;
    Arrays.sort(S);
    for(int i=0;i<S.length;i++)
    {
        int size = res.size();
        for(int j=0;j<size;j++)
        {
            ArrayList<Integer> item = new ArrayList<Integer>(res.get(j));
            item.add(S[i]);
            res.add(item);
        }
    }
    return res;
}

这种NP问题算法上都没有什么大的提高，基本上就是考察对于递归和非递归解法的理解，都是和N-Queens一个套路，掌握之后就没什么难度哈。

Sort Colors -- LeetCode

原题链接: http://oj.leetcode.com/problems/sort-colors/
这道题也是数组操作的题目，其实就是要将数组排序，只是知道数组中只有三个元素0,1,2。熟悉计数排序的朋友可能很快就发现这其实就是使用计数排序，元素空间只需要三个元素即可。代码如下：

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int[] res = new int[A.length];
    int[] helper = new int[3];
    for(int i=0;i<A.length;i++)
    {
        helper[A[i]]++;
    }
    for(int i=1;i<3;i++)
    {
        helper[i]=helper[i]+helper[i-1];
    }
    for(int i=A.length-1;i>=0;i--)
    {
        res[helper[A[i]]-1] = A[i];
        helper[A[i]]--;
    }
    for(int i=0;i<A.length;i++)
    {
        A[i] = res[i];
    }
}

上面的代码是计数排序的标准解法，可以看到总共进行了三次扫描，其实最后一次只是把结果数组复制到原数组而已，如果不需要in-place的结果只需要两次扫描。
其实就算返回元素组也可以是两次扫描，这需要用到元素只有0,1,2的本质。我们知道helper[i]中是包含着0,1,2的元素数量，我们只需要按照helper[0,1,2]的数量依次赋值过来即可（每层循环把helper[i]--，如果helper[i]到0就i++就可以了），只是这样就不是计数排序比较标准的解法，我希望还是复习一下。
这种方法的时间复杂度是O(2*n)，空间是O(k)，k是颜色的数量，这里是3。
上述方法需要两次扫描，我们考虑怎么用一次扫描来解决。其实还是利用了颜色是三种这一点，道理其实也简单，就是搞两个指针，一个指在当前0的最后一个下标，另一个是指在当前1的最后一个下标（2不需要指针因为剩下的都是2了）。进行一次扫描，如果遇到0就两个指针都前进一步并进行赋值，如果遇到1就后一个指针前进一步并赋值。代码如下：

public void sortColors(int[] A) {
    if(A==null || A.length==0)
        return;
    int idx0 = 0;
    int idx1 = 0;
    for(int i=0;i<A.length;i++)
    {
        if(A[i]==0)
        {
            A[i] = 2;
            A[idx1++] = 1;
            A[idx0++] = 0;
        }
        else if(A[i]==1)
        {
            A[i] = 2;
            A[idx1++] = 1;
        }
    }
}

上述方法时间复杂度还是O(n)，只是只需要一次扫描，空间上是O(1)（如果颜色种类是已知的话）。
这道题我觉得主要还是熟悉一下计数排序，计数排序是线性排序中比较重要的一种，关于排序要搞个专题专门的复习一下，很多排序的基本思想都对解题有帮助哈。

Search a 2D Matrix -- LeetCode

原题链接: http://oj.leetcode.com/problems/search-a-2d-matrix/
这道题是二分查找Search Insert Position的题目，因为矩阵是行有序并且列有序，查找只需要先按行查找，定位出在哪一行之后再进行列查找即可，所以就是进行两次二分查找。时间复杂度是O(logm+logn)，空间上只需两个辅助变量，因而是O(1)，代码如下：

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix == null || matrix.length==0 || matrix[0].length==0)
        return false;
    int l = 0;
    int r = matrix.length-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(matrix[mid][0] == target) return true;
        if(matrix[mid][0] > target)
        {
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    int row = r;
    if(row<0)
        return false;
    l = 0;
    r = matrix[0].length-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(matrix[row][mid] == target) return true;
        if(matrix[row][mid] > target)
        {
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }   
    return false;
}

二分查找是面试中出现频率不低的问题，但是很少直接考二分查找，会考一些变体，除了这道题，还有Search in Rotated Sorted Array和Search for a Range，思路其实差不多，稍微变化一下即可，有兴趣可以练习一下哈。