Clone Graph -- LeetCode

原题链接: http://oj.leetcode.com/problems/clone-graph/
这道题是LeetCode中为数不多的关于图的题目，不过这道题还是比较基础，就是考察图非常经典的方法：深度优先搜索和广度优先搜索。这道题用两种方法都可以解决，因为只是一个图的复制，用哪种遍历方式都可以。具体细节就不多说了，因为两种方法太常见了。这里恰好可以用旧结点和新结点的HashMap来做visited的记录。下面是广度优先搜索的代码：

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node==null)
        return null;
    LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
    map.put(node,copy);
    queue.offer(node);
    while(!queue.isEmpty())
    {
        UndirectedGraphNode cur = queue.poll();
        for(int i=0;i<cur.neighbors.size();i++)
        {
            if(!map.containsKey(cur.neighbors.get(i)))
            {
                copy = new UndirectedGraphNode(cur.neighbors.get(i).label);
                map.put(cur.neighbors.get(i),copy);
                queue.offer(cur.neighbors.get(i));
            }
            map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
        }
    }
    return map.get(node);
}

深度优先搜索的代码如下：

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node == null)
        return null;
    LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>();
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    stack.push(node);
    UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
    map.put(node,copy);
    while(!stack.isEmpty())
    {
        UndirectedGraphNode cur = stack.pop();
        for(int i=0;i<cur.neighbors.size();i++)
        {
            if(!map.containsKey(cur.neighbors.get(i)))
            {
                copy = new UndirectedGraphNode(cur.neighbors.get(i).label);
                map.put(cur.neighbors.get(i),copy);
                stack.push(cur.neighbors.get(i));
            }
            map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
        }
    }
    return map.get(node);
}

当然深度优先搜索也可以用递归来实现，代码如下：

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node == null)
        return null;
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
    map.put(node,copy);
    helper(node,map);
    return copy;
}
private void helper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map)
{
    for(int i=0;i<node.neighbors.size();i++)
    { 
        UndirectedGraphNode cur = node.neighbors.get(i);
        if(!map.containsKey(cur))
        {
            UndirectedGraphNode copy = new UndirectedGraphNode(cur.label);
            map.put(cur,copy);
            helper(cur,map);
        }
        map.get(node).neighbors.add(map.get(cur));
    }
}

这几种方法的时间复杂度都是O(n)（每个结点访问一次），而空间复杂度则是栈或者队列的大小加上HashMap的大小，也不会超过O(n)。图的两种遍历方式是比较经典的问题了，虽然在面试中出现的不多，但是还是有可能出现的，而且如果出现了就必须做好，所以大家还是得好好掌握哈。

Gas Station -- LeetCode

原题链接: http://oj.leetcode.com/problems/gas-station/
这是一道具体问题的题目，brute force的方法比较容易想到，就是从每一个站开始，一直走一圈，累加过程中的净余的油量，看它是不是有出现负的，如果有则失败，从下一个站开始重新再走一圈；如果没有负的出现，则这个站可以作为起始点，成功。可以看出每次需要扫描一圈，对每个站都要做一次扫描，所以时间复杂度是O(n^2)。代码比较直接，这里就不列举了。
接下来说说如何提高这个算法。方法主要思想是把这个圈划分成一个个的负序列，以及一个正序列（如果存在的话）。从任意一个站出发，我们可以累加油的净余量，如果出现负的，序列结束，开启一个新的，并且证明旧的这个序列的起点不能作为起点，因为会出现负油量，不能继续前进。下面我们证明
不仅这个负序列的起点不能作为起点，负序列中的任意一点都不能作为起点。
证明：假设我们取定负序列中的一个站作为起点，因为一个序列一旦遇到负的净余量就会结束并且开启新的，那么说明在这个起点前的累加结果必然是正数（否则会结束这个序列，则前面不会是这个序列的一部分）。如此我们从当前序列出发必然会使走到序列终点时负的油量更大，本来已经是负的，所以不能去负序列的任意一个结点作为起点。
根据上面的划分方式，我们会把圈分成一段段的序列，而且其中最多只有一个正序列，那就是绕一圈回到起点的那个序列（当然也有可能整个圈是一个正序列，就是油量一直为正，那么我们测的开始点就可以作为起点了）。接下来我们证明
如果将全部油量累计起来，总量为正，那么一定能找到一个起点，使得可以走完一圈，也就是一定有解。
证明：按照我们之前的划分，整个圈会被划分成有累积量为s1, s2, ..., sk 的负序列，以及一个正序列拥有油量sp（这里正序列一定存在因为全部累加和是正的，如果全是负序列那么结果不会是正的）。而且我们知道s1+s2+...+sk+sp>0，也就是说sp>-s1-s2-...-sk。换句话说，如果我们从sp对应的站的起点出发，在sp对应的序列会一直是正的，并且，当他走到负序列时，因为sp的正油量大于所有负油量的总和，所以累加油量会一直正，完整整个圈的行驶。这证明了只要累加油量是正的，一定能找到一个起点来完成任务。
根据上面的两个命题，我们可以来实现代码，需要维护两个量，一个是总的累积油量total，另一个是当前序列的累计油量sum，如果出现负的，则切换起点，并且将sum置0。总共是需要扫描所有站一次，时间复杂度是O(n)。而只需要两个额外变量，空间复杂度是O(1)。代码如下：

public int canCompleteCircuit(int[] gas, int[] cost) {
    if(gas==null || gas.length==0 || cost==null || cost.length==0 || gas.length!=cost.length)
        return -1;
    int sum = 0;
    int total = 0;
    int pointer = -1;
    for(int i=0;i<gas.length;i++)
    {
        int diff = gas[i]-cost[i];
        sum += diff;
        total += diff;
        if(sum<0)
        {
            sum=0;
            pointer=i;
        }
    }
    return total>=0?pointer+1:-1;
}

这个题目的优化解法更像是一个数学题，需要定义数学模型并证明命题正确性，比较需要数学逻辑的功底。通过定义的模型以及证明的命题来做一部分贪心。

Single Number -- LeetCode

原题链接: http://oj.leetcode.com/problems/single-number/
这道题目跟Single Number II比较类似，区别只是这道题目每个元素出现两次，而不是三次。我们仍然可以按照Single Number II中的两种方法来，都只是把取余3改成取余2即可。我们就列举一下第二种方法的代码如下：

public int singleNumber(int[] A) {
    int[] digits = new int[32];
    for(int i=0;i<32;i++)
    {
        for(int j=0;j<A.length;j++)
        {
            digits[i] += (A[j]>>i)&1;
        }
    }
    int res = 0;
    for(int i=0;i<32;i++)
    {
        res += (digits[i]%2)<<i;
    }
    return res;
}

上面方法的时间复杂度仍然是O(n)，空间是一个32个元素的数组，是O(1)的复杂度。
按照上面的方法，虽然空间复杂度是O(1)的，不过还是需要一个32个元素的数组。还有另一种方法是利用每个元素出现两次，以及位操作异或的性质来解决这个问题。因为两个相同的元素异或结果是0，利用这个特点我们可以对所有数组元素进行异或，如果出现两次的元素就会自行抵消，而最终剩下的元素则是出现一次的元素。这个方法只需要一次扫描，即O(n)的时间复杂度，而空间上也不需要任何额外变量，比起上面的方法更优。代码如下：

public int singleNumber(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int res = A[0];
    for(int i=1;i<A.length;i++)
    {
        res ^= A[i];
    }
    return res;
}

上面的方法实现非常简练，不过也相当取巧，可能没有准备过比较难在面试中想到。相对而言第一种方法是比较通用的，无论出现多少次都是适用的。第二种方法属于对于出现两次这种特殊情况才能使用，不过方法巧妙，有点体现位运算的精髓，所以个人还是挺喜欢的哈。

Single Number II -- LeetCode

原题链接: http://oj.leetcode.com/problems/single-number-ii/
这个题比较直接的想法是用一个HashMap对于出现的元素进行统计，key是元素，value是出现个数，如果元素出现三次，则从HashMap中移除，最后在HashMap剩下来的元素就是我们要求的元素（因为其他元素都出现三次，有且仅有一个元素不是如此）。这样需要对数组进行一次扫描，所以时间复杂度是O(n)，而需要一个哈希表来统计元素数量，总共有(n+2)/3个元素，所以空间复杂度是O((n+2)/3)=O(n)。这个方法非常容易实现，就不列举代码了。
在LeetCode的题目中要求我们不要用额外空间来实现，也就是O(1)空间复杂度。实现的思路是基于数组的元素是整数，我们通过统计整数的每一位来得到出现次数。我们知道如果每个元素重复出现三次，那么每一位出现1的次数也会是3的倍数，如果我们统计完对每一位进行取余3，那么结果中就只剩下那个出现一次的元素。总体只需要对数组进行一次线性扫描，统计完之后每一位进行取余3并且将位数字赋给结果整数，这是一个常量操作（因为整数的位数是固定32位），所以时间复杂度是O(n)。而空间复杂度需要一个32个元素的数组，也是固定的，因而空间复杂度是O(1)。代码如下：

public int singleNumber(int[] A) {
    int[] digits = new int[32];
    for(int i=0;i<32;i++)
    {
        for(int j=0;j<A.length;j++)
        {
            digits[i] += (A[j]>>i)&1;
        }
    }
    int res = 0;
    for(int i=0;i<32;i++)
    {
        res += (digits[i]%3)<<i;
    }
    return res;
}

这个题目主要是对整数数组的操作，用到的位统计是整数中经常使用的技巧，利用位的固定性来省去一定的时间或者空间复杂度。

Copy List with Random Pointer -- LeetCode

原题链接: http://oj.leetcode.com/problems/copy-list-with-random-pointer/
这是一道链表操作的题目，要求复制一个链表，不过链表的每个结点带有一个随机指针，指向某一个结点。
我们先介绍一种比较直接的算法，思路是先按照复制一个正常链表的方式复制，复制的时候把复制的结点做一个HashMap，以旧结点为key，新节点为value。这么做的目的是为了第二遍扫描的时候我们按照这个哈希表把结点的随机指针接上。这个算法是比较容易想到的，总共要进行两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个哈希表来做结点的映射，所以空间复杂度也是O(n)。代码如下：

public RandomListNode copyRandomList(RandomListNode head) {
    if(head == null)
        return head;
    HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
    RandomListNode newHead = new RandomListNode(head.label);
    map.put(head,newHead);
    RandomListNode pre = newHead;
    RandomListNode node = head.next;
    while(node!=null)
    {
        RandomListNode newNode = new RandomListNode(node.label);
        map.put(node,newNode);
        pre.next = newNode;
        pre = newNode;
        node = node.next;
    }
    node = head;
    RandomListNode copyNode = newHead;
    while(node!=null)
    {
        copyNode.random = map.get(node.random);
        copyNode = copyNode.next;
        node = node.next;
    }
    return newHead;
}

那么有没有办法可以不用额外空间来完成这个任务呢？还是有的，前面我们需要一个哈希表的原因是当我们访问一个结点时可能它的随机指针指向的结点还没有访问过，结点还没有创建，所以我们需要线性的额外空间。想避免使用额外空间，我们只能通过利用链表原来的数据结构来存储结点。基本思路是这样的，对链表进行三次扫描，第一次扫描对每个结点进行复制，然后把复制出来的新节点接在原结点的next，也就是让链表变成一个重复链表，就是新旧更替；第二次扫描中我们把旧结点的随机指针赋给新节点的随机指针，因为新结点都跟在旧结点的下一个，所以赋值比较简单，就是node.next.random = node.random.next，其中node.next就是新结点，因为第一次扫描我们就是把新结点接在旧结点后面。现在我们把结点的随机指针都接好了，最后一次扫描我们把链表拆成两个，第一个还原原链表，而第二个就是我们要求的复制链表。因为现在链表是旧新更替，只要把每隔两个结点分别相连，对链表进行分割即可。这个方法总共进行三次线性扫描，所以时间复杂度是O(n)。而这里并不需要额外空间，所以空间复杂度是O(1)。比起上面的方法，这里多做一次线性扫描，但是不需要额外空间，还是比较值的。实现的代码如下：

public RandomListNode copyRandomList(RandomListNode head) {
    if(head == null)
        return head;
    RandomListNode node = head;
    while(node!=null)
    {
        RandomListNode newNode = new RandomListNode(node.label);
        newNode.next = node.next;
        node.next = newNode;
        node = newNode.next;
    }
    node = head;
    while(node!=null)
    {
        if(node.random != null)
            node.next.random = node.random.next;
        node = node.next.next;
    }
    RandomListNode newHead = head.next;
    node = head;
    while(node != null)
    {
        RandomListNode newNode = node.next;
        node.next = newNode.next;
        if(newNode.next!=null)
            newNode.next = newNode.next.next;
        node = node.next;
    }
    return newHead;
}

上面介绍了两种方法来解决这个问题，第二种方法利用了原来的链表省去了额外空间，虽然多进行一次扫描，不过对时间复杂度量级没有影响，还是对算法有提高的。这个题目算是比较有难度的链表题目，既有基本操作，也需要一些算法思想。

Word Break II -- LeetCode

原题链接: http://oj.leetcode.com/problems/word-break-ii/
这道题目要求跟Word Break比较类似，不过返回的结果不仅要知道能不能break，如果可以还要返回所有合法结果。一般来说这种要求会让动态规划的效果减弱很多，因为我们要在过程中记录下所有的合法结果，中间的操作会使得算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面需要历史信息会取不到。所以这道题目我们介绍两种方法，一种是直接brute force用递归解，另一种是跟Word Break思路类似的动态规划。
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。代码如下：

public ArrayList<String> wordBreak(String s, Set<String> dict) {
    ArrayList<String> res = new ArrayList<String>();
    if(s==null || s.length()==0)
        return res;
    helper(s,dict,0,"",res);
    return res;
}
private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)
{
    if(start>=s.length())
    {
        res.add(item);
        return;
    }
    StringBuilder str = new StringBuilder();
    for(int i=start;i<s.length();i++)
    {
        str.append(s.charAt(i));
        if(dict.contains(str.toString()))
        {
            String newItem = item.length()>0?(item+" "+str.toString()):str.toString();
            helper(s,dict,i+1,newItem,res);
        }
    }
}

接下来我们列出动态规划的解法，递推式跟Word Break是一样的，只是现在不只要保存true或者false，还需要保存true的时候所有合法的组合，以便在未来需要的时候可以得到。不过为了实现这点，代码量就增大很多，需要一个数据结构来进行存储，同时空间复杂度变得非常高，因为所有中间组合都要一直保存。时间上还是有提高的，就是当我们需要前面到某一个元素前的所有合法组合时，我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。代码如下：

class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
        this.start = start; this.end = end;
    }
    public Interval(Interval i) {
        start = i.start;
        end = i.end;
 }
}
ArrayList<ArrayList<Interval>> deepCopy(ArrayList<ArrayList<Interval>> paths) {
    if (paths==null) return null;
    ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>(paths.size());
    for (int i=0; i<paths.size(); i++) {
     ArrayList<Interval> path = paths.get(i);
     ArrayList<Interval> copy = new ArrayList<Interval>(path.size());
        for (int j=0; j<path.size(); j++) {
         copy.add(new Interval(path.get(j)));
     }
     res.add(copy);
    }
    return res;
}
public ArrayList<String> wordBreak(String s, Set<String> dict) {
    ArrayList<String> res = new ArrayList<String>();
    if (s==null || s.length()==0) return res;
    Map<Integer, ArrayList<ArrayList<Interval>>> dp = new HashMap<Integer, ArrayList<ArrayList<Interval>>>();
    dp.put(0, new ArrayList<ArrayList<Interval>>());
    dp.get(0).add(new ArrayList<Interval>());
    for (int i=1; i<=s.length(); i++) {
        for (int j=0; j<i; j++) {
            String cur = s.substring(j, i);
            ArrayList<ArrayList<Interval>> paths = null;
            if (dp.containsKey(j) && dict.contains(cur)) {
                paths = deepCopy(dp.get(j));
                Interval interval = new Interval(j, i);
                for (ArrayList<Interval> path:paths) {
                    path.add(interval);
                }
            }
            if (paths != null) {
                if (!dp.containsKey(i)) {
                    dp.put(i, paths);
                } 
                else {
              dp.get(i).addAll(paths);
             }
            }
        }
    }
    if (!dp.containsKey(s.length())) {
        return res;
    }
    ArrayList<ArrayList<Interval>> paths = dp.get(s.length());
    for (int j=0; j<paths.size(); j++) {
        ArrayList<Interval> path = paths.get(j);
        StringBuilder str = new StringBuilder();
        for (int i=0; i<path.size(); i++) {
            if (i!=0) {str.append(" ");}
            int start = path.get(i).start;
            int end = path.get(i).end;
            str.append(s.substring(start, end));
        }
        res.add(str.toString());
    }
    return res;
}

可以看出，用动态规划的代码复杂度要远远高于brute force的解法，而且本质来说并没有很大的提高，甚至空间上还是一个暴涨的情况。所以这道题来说并不是一定要用动态规划，有一个朋友在面Amazon时遇到这道题，面试官并没有要求动态规划，用brute force即可，不过两种方法时间上和空间上的优劣还是想清楚比较好，面试官可能想听听理解。实现的话可能主要是递归解法。
还有一点需要指出的是，上面的两个代码放到LeetCode中都会超时，原因是LeetCode中有一个非常tricky的测试case，其实是不能break的，但是又很长，出现大量的记录和回溯，因此一般通过这个的解法是把Word Break先跑一遍，判断是不是能break，如果可以再跑上面的代码。这样做法其实比较傻，但是为了过这个只能这样了，这一点我觉得LeetCode没必要把超时设得这么严格，实际意义不大，只是把AC率给拉了下来哈。

Plus One -- LeetCode

原题链接: http://oj.leetcode.com/problems/plus-one/
这是一道比较简单的题目，对一个数组进行加一操作。但是可不要小看这个题，这个题被称为“Google最喜欢的题”，因为在google面试中出现的频率非常高。我们先说说这道题的解法。思路是维护一个进位，对每一位进行加一，然后判断进位，如果有继续到下一位，否则就可以返回了，因为前面不需要计算了。有一个小细节就是如果到了最高位进位仍然存在，那么我们必须重新new一个数组，然后把第一个为赋成1（因为只是加一操作，其余位一定是0，否则不会进最高位）。因为只需要一次扫描，所以算法复杂度是O(n)，n是数组的长度。而空间上，一般情况是O(1)，但是如果数是全9，那么是最坏情况，需要O(n)的额外空间。代码如下：

public int[] plusOne(int[] digits) {
    if(digits == null || digits.length==0)
        return digits;
    int carry = 1;
    for(int i=digits.length-1;i>=0;i--)
    {
        int digit = (digits[i]+carry)%10; 
        carry = (digits[i]+carry)/10;
        digits[i] = digit;
        if(carry==0)
            return digits;    
    }
    int [] res = new int[digits.length+1];    
    res[0] = 1;
    return res;
}

我自己在Google的电面中就遇到了这道题，我觉得为什么Google喜欢的原因是后续可以问一些比较基本的扩展问题，比如可以扩展这个到两个数组相加，或者问一些OO设计，假设现在要设计一个BigInteger类，那么需要什么构造函数，然后用什么数据结构好，用数组和链表各有什么优劣势。这些问题虽然不是很难，但是可以考到一些基本的理解，所以平时准备有机会还是可以多想想哈。

Word Break -- LeetCode

原题链接: http://oj.leetcode.com/problems/word-break/
这道题仍然是动态规划的题目，我们总结一下动态规划题目的基本思路。首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。
接下来我们套用上面的思路来解这道题。首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true，写成式子是

假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。代码如下：

public boolean wordBreak(String s, Set<String> dict) {
    if(s==null || s.length()==0)
        return true;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int i=0;i<s.length();i++)
    {
        StringBuilder str = new StringBuilder(s.substring(0,i+1));
        for(int j=0;j<=i;j++)
        {
            if(res[j] && dict.contains(str.toString()))
            {
                res[i+1] = true;
                break;
            }
            str.deleteCharAt(0);
        }
    }
    return res[s.length()];
}

动态规划的题目在LeetCode中占有相当的比例，不过却没有什么通法，因为每道题会有不同的性质和获取信息的角度。但是总体来说基本思路就如同我上面介绍的那样，根据步骤出来之后基本上问题也就解决了，大家可以多练习熟悉一下哈。

Minimum Path Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/minimum-path-sum/
这道题跟Unique Paths，Unique Paths II是相同类型的。事实上，这道题是上面两道题的general版本，是寻找带权重的path。在Unique Paths中，我们假设每个格子权重都是1，而在Unique Paths II中我们假设障碍格子的权重是无穷大，所以永远不会选择。剩下的区别就是这道题寻找这些路径中权重最小的，而不是总路径数。其实方法是一样的，还是使用动态规划，只是现在维护的不是路径数，而是到达某一个格子的最短路径（也就是权重之和最小）。而这个当前最短路径可以取前面一格和上面一格中小的最短路径长度得到，因此递推式是res[i][j]=min(res[i-1][j], res[i][j-1])+grid[i][j]。总共进行两层循环，时间复杂度是O(m*n)。而空间复杂度仍是使用Unique Paths中的方法来省去一维，是O(m)，不了解的朋友可以看看哈。代码如下：

public int minPathSum(int[][] grid) {
    if(grid == null || grid.length==0 || grid[0].length==0)
        return 0;
    int[] res = new int[grid[0].length];
    res[0] = grid[0][0];
    for(int i=1;i<grid[0].length;i++)
    {
        res[i] = res[i-1]+grid[0][i];
    }
    for(int i=1;i<grid.length;i++)
    {
        for(int j=0;j<grid[0].length;j++)
        {
            if(j==0)
                res[j] += grid[i][j];
            else
                res[j] = Math.min(res[j-1], res[j])+grid[i][j];
        }
    }
    return res[grid[0].length-1];
}

这道题是动态规划的经典题型，模型足够简单，所以可能在简单的面试（比如电面）出现。总体来说还是比较容易的，递推式比较直观。

Insert Interval -- LeetCode

原题链接: http://oj.leetcode.com/problems/insert-interval/
这道题跟Merge Intervals很类似，都是关于数据结构interval的操作。事实上，Merge Intervals是这道题的子操作，就是插入一个interval，如果出现冲突了，就进行merge。跟Merge Intervals不一样的是，这道题不需要排序，因为插入之前已经默认这些intervals排好序了。简单一些的是这里最多只有一个连续串出现冲突，因为就插入那么一个。基本思路就是先扫描走到新的interval应该插入的位置，接下来就是插入新的interval并检查后面是否冲突，一直到新的interval的end小于下一个interval的start，然后取新interval和当前interval中end大的即可。因为要进行一次线性扫描，所以时间复杂度是O(n)。而空间上如果我们重新创建一个ArrayList返回，那么就是O(n)。有朋友可能会说为什么不in-place的进行操作，这样就不需要额外空间，但是如果使用ArrayList这个数据结构，那么删除操作是线性的，如此时间就不是O(n)的。如果这道题是用LinkedList那么是可以做到in-place的，并且时间是线性的。代码如下：

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> res = new ArrayList<Interval>();
    if(intervals.size()==0)
    {
        res.add(newInterval);
        return res;
    }
    int i=0;
    while(i<intervals.size() && intervals.get(i).end<newInterval.start)
    {
        res.add(intervals.get(i));
        i++;
    }
    if(i<intervals.size())
        newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
    res.add(newInterval);
    while(i<intervals.size() && intervals.get(i).start<=newInterval.end)
    {
        newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
        i++;
    }
    while(i<intervals.size())
    {
        res.add(intervals.get(i));
        i++;
    }
    return res;
}

这道题有一个变体，就是如果插入的时候发现冲突，那就返回失败，不插入了。看起来好像比上面这道题还要简单，但是要注意的是，如此我们就不需要进行线性扫描了，而是进行二分查找，如果不冲突，则进行插入，否则直接返回失败。这样时间复杂度可以降低到O(logn)。当然这里需要用二分查找树去维护这些intervals。所以一点点变化可能可以使复杂度降低，还是应该多做思考哈。
同时，这种题目还可以问一些关于OO设计的东西，比如就直接问你要实现一个intervals的类，要维护哪些变量，实现哪些功能，用什么数据结构，等等。这些你可以跟面试官讨论，然后根据他的功能要求用相应的数据结构。所以扩展性还是很强的，大家可以考虑的深入一些。

Unique Paths II -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-paths-ii/
这道题跟Unique Paths非常类似，只是这道题给机器人加了障碍，不是每次都有两个选择（向右，向下）了。因为有了这个条件，所以Unique Paths中最后一个直接求组合的方法就不适用了，这里最好的解法就是用动态规划了。递推式还是跟Unique Paths一样，只是每次我们要判断一下是不是障碍，如果是，则res[i][j]=0，否则还是res[i][j]=res[i-1][j]+res[i][j-1]。实现中还是只需要一个一维数组，因为更新的时候所需要的信息足够了。这样空间复杂度是是O(n)（如同Unique Paths中分析的，如果要更加严谨，我们可以去行和列中小的那个，然后把小的放在内层循环，空间复杂度就是O(min(m,n))，时间复杂度还是O(m*n)。代码如下：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if(obstacleGrid == null || obstacleGrid.length==0 || obstacleGrid[0].length==0)
        return 0;
    int[] res = new int[obstacleGrid[0].length];
    res[0] = 1;
    for(int i=0;i<obstacleGrid.length;i++)
    {
        for(int j=0;j<obstacleGrid[0].length;j++)
        {
            if(obstacleGrid[i][j]==1)
            {
                res[j]=0;
            }
            else
            {
                if(j>0)
                    res[j] += res[j-1];
            }
        }
    }
    return res[obstacleGrid[0].length-1];
}

这里就不列出brute force递归方法的代码了，递归式和结束条件跟动态规划很近似，有兴趣的朋友可以写一下哈。

Unique Paths -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-paths/
这道题是比较典型的动态规划的题目。模型简单，但是可以考核动态规划的思想。
我们先说说brute force的解法，比较容易想到用递归，到达某一格的路径数量等于它的上面和左边的路径数之和，结束条件是走到行或者列的边缘。因为每条路径都会重新探索，时间复杂度是结果数量的量级，不是多项式的复杂度。代码如下：

public int uniquePaths(int m, int n) {
    return helper(1,1,m,n);
}
private int helper(int row, int col, int m, int n)
{
    if(row==m && col==n)
        return 1;
    if(row>m || col>n)
        return 0;
    return helper(row+1,col,m,n)+helper(row,col+1,m,n);
}

上面的代码放到LeetCode中跑会超时，因为不是多项式量级的。其实上一步中递推式已经出来了，就是res[i][j]=res[i-1][j]+res[i][j-1]，这样我们就可以用一个数组来保存历史信息，也就是在i行j列的路径数，这样每次就不需要重复计算，从而降低复杂度。用动态规划我们只需要对所有格子进行扫描一次，到了最后一个得到的结果就是总的路径数，所以时间复杂度是O(m*n)。而对于空间可以看出我们每次只需要用到上一行当前列，以及前一列当前行的信息，我们只需要用一个一维数组存上一行的信息即可，然后扫过来依次更替掉上一行对应列的信息即可（因为所需要用到的信息都还没被更替掉），所以空间复杂度是O(n)（其实如果要更加严谨，我们可以去行和列中小的那个，然后把小的放在内层循环，这样空间复杂度就是O(min(m,n))，下面的代码为了避免看起来过于繁杂，就不做这一步了，有兴趣的朋友可以实现一下，比较简单，不过代码有点啰嗦）。实现的代码如下：

public int uniquePaths(int m, int n) {
    if(m<=0 || n<=0)
        return 0;
    int[] res = new int[n];
    res[0] = 1;
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
           res[j] += res[j-1];
        }
    }
    return res[n-1];
}

上面的方法用动态规划来求解，如果我们仔细的看这个问题背后的数学模型，其实就是机器人总共走m+n-2步，其中m-1步往下走，n-1步往右走，本质上就是一个组合问题，也就是从m+n-2个不同元素中每次取出m-1个元素的组合数。根据组合的计算公式，我们可以写代码来求解即可。代码如下：

public int uniquePaths(int m, int n) {
    double dom = 1;
    double dedom = 1;
    int small = m<n? m-1:n-1;
    int big = m<n? n-1:m-1;
    for(int i=1;i<=small;i++)
    {
        dedom *= i;
        dom *= small+big+1-i;
    }
    return (int)(dom/dedom);
}

上面的代码求解了组合的结果，只需要做一次行或者列的扫描，所以时间复杂度是O(min(m,n))，而空间复杂度是O(1)。比起上面的两种解法更优。不过这里有个弊端，就是如果代码中的dom和dedom如果不是double，而是用int，那么会很容易越界，因为这是一个阶乘，所以大家在面试中讨论这种方法要注意和提及越界的问题。
上面介绍了几种方法来求解这个问题，其实都是比较简单的模型，只是提供了不同的思路。Unique Paths II是这道题的扩展，给机器人增加了障碍，有兴趣的朋友可以联系一下。

Permutation Sequence -- LeetCode

原题链接: http://oj.leetcode.com/problems/permutation-sequence/
这道题目算法上没有什么特别的，更像是一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。代码如下：

public String getPermutation(int n, int k) {
    if(n<=0)
        return "";
    k--;
    StringBuilder res = new StringBuilder();
    int factorial = 1;
    ArrayList<Integer> nums = new ArrayList<Integer>();
    for(int i=2;i<n;i++)
    {
        factorial *= i;
    }
    for(int i=1;i<=n;i++)
    {
        nums.add(i);
    }
    int round = n-1;
    while(round>=0)
    {
        int index = k/factorial;
        k %= factorial;
        res.append(nums.get(index));
        nums.remove(index);
        if(round>0)
            factorial /= round;
        round--;
    }
    return res.toString();
}

上面代码还有有个小细节，就是一开始把k--，目的是让下标从0开始，这样下标就是从0到n-1，不用考虑n时去取余，更好地跟数组下标匹配。如果有朋友有更好的思路来实现线性的时间复杂度，欢迎指教哈，可以留言或者发邮件到linhuanmars@gmail.com给我。

Binary Tree Postorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-postorder-traversal/
跟Binary Tree Inorder Traversal以及Binary Tree Preorder Traversal一样，二叉树的后序遍历我们还是介绍三种方法，第一种是递归，第二种是迭代方法，第三种是用线索二叉树。 递归还是那么简单，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。代码如下：

public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    helper(root, res);
    return res;
}
private void helper(TreeNode root, ArrayList<Integer> res)
{
    if(root == null)
        return;
    helper(root.left,res);
    helper(root.right,res);
    res.add(root.val);
}

接下来是迭代的做法，本质就是用一个栈来模拟递归的过程，但是相比于Binary Tree Inorder Traversal和Binary Tree Preorder Traversal，后序遍历的情况就复杂多了。我们需要维护当前遍历的cur指针和前一个遍历的pre指针来追溯当前的情况（注意这里是遍历的指针，并不是真正按后序访问顺序的结点）。具体分为几种情况：
（1）如果pre的左孩子或者右孩子是cur，那么说明遍历在往下走，按访问顺序继续，即如果有左孩子，则是左孩子进栈，否则如果有右孩子，则是右孩子进栈，如果左右孩子都没有，则说明该结点是叶子，可以直接访问并把结点出栈了。
（2）如果反过来，cur的左孩子是pre，则说明已经在回溯往上走了，但是我们知道后序遍历要左右孩子走完才可以访问自己，所以这里如果有右孩子还需要把右孩子进栈，否则说明已经到自己了，可以访问并且出栈了。
（3）如果cur的右孩子是pre，那么说明左右孩子都访问结束了，可以轮到自己了，访问并且出栈即可。
算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。实现的代码如下：

public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    stack.push(root);
    TreeNode pre = null;
    while(!stack.isEmpty())
    {
        TreeNode cur = stack.peek();
        if(pre==null || pre.left==cur || pre.right==cur)
        {
            if(cur.left!=null)
            {
                stack.push(cur.left);
            }
            else if(cur.right!=null)
            {
                stack.push(cur.right);
            }
            else
            {
                res.add(cur.val);
                stack.pop();
            }
        }
        else if(cur.left==pre && cur.right!=null)
        {
            stack.push(cur.right);
        }
        else
        {
            res.add(cur.val);
            stack.pop();
        }
        pre = cur;
    }
    return res;
}

上面迭代实现的思路虽然清晰，但是实现起来还是分情况太多，不容易记忆。我后来再看wiki的时候发现有跟Binary Tree Inorder Traversal和Binary Tree Preorder Traversal非常类似的解法，容易统一进行记忆，思路可以参考其他两种，区别是最下面在弹栈的时候需要分情况一下：
1）如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点），那么就把当前结点移到右结点继续循环；
2）如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕，应该访问自己继续回溯了。
下面列举一下代码：

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
    {
        return res;
    }
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    TreeNode pre = null;
    while(root != null || !stack.isEmpty())
    {
        if(root!=null)
        {
            stack.push(root);
            root = root.left;
        }
        else
        {
            TreeNode peekNode = stack.peek();
            if(peekNode.right!=null && pre != peekNode.right)
            {
                root = peekNode.right;
            }
            else
            {
                stack.pop();
                res.add(peekNode.val);
                pre = peekNode;
            }
        }
    }
    return res;
}

最后介绍Morris遍历方法，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了，所以优势在于不需要额外空间。不过同样相比于Binary Tree Inorder Traversal和Binary Tree Preorder Traversal，后序遍历的情况要复杂得多，因为后序遍历中一直要等到孩子结点访问完才能访问自己，需要一些技巧来维护。
在这里，我们需要创建一个临时的根节点dummy，把它的左孩子设为树的根root。同时还需要一个subroutine来倒序输出一条右孩子路径上的结点。跟迭代法一样我们需要维护cur指针和pre指针来追溯访问的结点。具体步骤是重复以下两步直到结点为空：
1. 如果cur指针的左孩子为空，那么cur设为其右孩子。
2. 否则，在cur的左子树中找到中序遍历下的前驱结点pre（其实就是左子树的最右结点）。接下来分两种子情况：
（1）如果pre没有右孩子，那么将他的右孩子接到cur。将cur更新为它的左孩子。
（2）如果pre的右孩子已经接到cur上了，说明这已经是回溯访问了，可以处理访问右孩子了，倒序输出cur左孩子到pre这条路径上的所有结点，并把pre的右孩子重新设为空（结点已经访问过了，还原现场）。最后将cur更新为cur的右孩子。
空间复杂度同样是O(1)，而时间复杂度也还是O(n)，倒序输出的过程只是加大了常数系数，并没有影响到时间的量级。如果对这个复杂度结果不是很熟悉的朋友，可以先看看Binary Tree Inorder Traversal中的分析，在那个帖子中讲得比较详细。实现的代码如下：

public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    TreeNode dummy = new TreeNode(0);
    dummy.left = root;
    TreeNode cur = dummy;
    TreeNode pre = null;
    while(cur!=null)
    {
        if (cur.left==null)
        {
            cur = cur.right;
        }
        else
        {
            pre = cur.left;
            while (pre.right!=null && pre.right!=cur)
                pre = pre.right;
            if (pre.right==null)
            {
                pre.right = cur;
                cur = cur.left;
            }
            else
            {
                reverse(cur.left, pre);
                TreeNode temp = pre;
                while (temp != cur.left)
                {
                    res.add(temp.val);
                    temp = temp.right;
                }
                res.add(temp.val);
                reverse(pre, cur.left);
                pre.right = null;
                cur = cur.right;
            }
        }
    } 
    return res;
}
void reverse(TreeNode start, TreeNode end) 
{
    if (start == end)
        return;
    TreeNode pre = start;
    TreeNode cur = start.right;
    TreeNode next;
    while (pre != end)
    {
        next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
}

到目前为止，二叉树的三种遍历的三种方法都介绍过了，后序遍历相比于前面两种，还是要复杂一些，个人觉得面试中可能倾向于靠其他两种遍历，特别是像Morris遍历方法，如果没有准备过很难在面试中写出这种方法的后序遍历，主要还是要有概念，就是知道方法的存在性以及优劣的分析就可以了，不过递归法和迭代法还是需要掌握一下的。

Spiral Matrix II -- LeetCode

原题链接: http://oj.leetcode.com/problems/spiral-matrix-ii/
这道题跟Spiral Matrix很类似，只是这道题是直接给出1到n^2，然后把这些数按照螺旋顺序放入数组中。思路跟Spiral Matrix还是一样的，就是分层，然后按照上右下左的顺序放入数组中。每个元素只访问一次，时间复杂度是O(n^2)。代码如下：

public int[][] generateMatrix(int n) {
    if(n<0)
        return null;
    int[][] res = new int[n][n];
    int levelNum = n/2;
    int num = 1;
    for(int l=0;l<levelNum;l++)
    {
        for(int i=l;i<n-l;i++)
        {
            res[l][i] = num++;
        }
        for(int i=l+1;i<n-l;i++)
        {
            res[i][n-1-l] = num++;
        }
        for(int i=n-2-l;i>=l;i--)
        {
            res[n-1-l][i] = num++;
        }
        for(int i=n-2-l;i>l;i--)
        {
            res[i][l] = num++;
        }
    }
    if(n%2==1)
    {
        res[levelNum][levelNum] = num;
    }
    return res;
}

这种题目就是简单的数组操作，主要是得细心，注意数组下标即可。

Rotate List -- LeetCode

原题链接: http://oj.leetcode.com/problems/rotate-list/
这是一道链表操作的题目，基本思路是用walker-runner定位到要旋转的那个结点，然后将下一个结点设为新表头，并且把当前结点设为表尾。需要注意的点就是旋转的结点数可能超过链表长度，所以我们要对这个进行取余。定位旋转的尾结点的不超过链表的长度，所以时间复杂度是O(n)，空间复杂度是O(1)。代码如下：

public ListNode rotateRight(ListNode head, int n) {
    if(head == null)
    {
        return null;
    }
    ListNode walker = head;
    ListNode runner = head;
    int idx = 0;
    while(runner!=null && idx<n)
    {
        runner = runner.next;
        idx++;
    }
    if(runner == null)
    {
        n %= idx;
        runner = head;
        idx=0;
        while(runner!=null && idx<n)
        {
            runner = runner.next;
            idx++;
        }
    }
    while(runner.next!=null)
    {
        walker = walker.next;
        runner = runner.next;
    }
    runner.next = head;
    ListNode newHead = walker.next;
    walker.next = null;
    return newHead;
}

上面的实现中采取的方式是直接走到那个结点，如果没超过长度就直接旋转了，如果超过了，就进行取余，并且重新跑到结尾点。其实也可以先直接求长度，然后取余之后再走。其实各有利弊，所以大家根据喜好实现即可哈。

Length of Last Word -- LeetCode

原题链接: http://oj.leetcode.com/problems/length-of-last-word/
这道题比较简单，就是进行一下字符串操作。唯一的细节就是要去掉尾部的空格，然后读到下一个空格，记录下长度。时间复杂度是O(n)，n是字符串的长度，空间复杂度是O(1)。代码如下：

public int lengthOfLastWord(String s) {
    if(s==null || s.length()==0)
        return 0;
    int idx = s.length()-1;
    while(idx>=0 && s.charAt(idx)==' ') idx--;
    int idx2 = idx;
    while(idx2>=0 && s.charAt(idx2)!=' ') idx2--;
    return idx-idx2;
}

这样子的题目比较简单，考查最简单的代码实现，一般也就是面试的第一道最基础的题目，这种题目要细心，实现不可以有bug哈。

Merge Intervals -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-intervals/
这是一道关于interval数组结构的操作，在面试中也是一种比较常见的数据结构。假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。代码如下：

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    ArrayList<Interval> res = new ArrayList<Interval>();
    if(intervals==null || intervals.size()==0)
        return intervals;
    Comparator<Interval> comp = new Comparator<Interval>()
    {
        @Override
        public int compare(Interval i1, Interval i2)
        {
            if(i1.start==i2.start)
                return i1.end-i2.end;
            return i1.start-i2.start;
        }
    };
    Collections.sort(intervals,comp);
    
    res.add(intervals.get(0));
    for(int i=1;i<intervals.size();i++)
    {
        if(res.get(res.size()-1).end>=intervals.get(i).start)
        {
            res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(i).end);
        }
        else
        {
            res.add(intervals.get(i));
        }
    }
    return res;
}

自定义Comparator有时候在面试中也会要求实现，不熟悉的朋友还是要熟悉一下哈。LeetCode中关于interval的题目还有Insert Interval，有兴趣的朋友可以看看哈。

Spiral Matrix -- LeetCode

原题链接: http://oj.leetcode.com/problems/spiral-matrix/
这道题是比较简单的数组操作，按螺旋顺序把数组读取并且放到结果数组中即可。基本思路跟Rotate Image有点类似，就是一层一层的处理，每一层都是按照右下左上的顺序进行读取就可以。实现中要注意两个细节，一个是因为题目中没有说明矩阵是不是方阵，因此要先判断一下行数和列数来确定螺旋的层数。另一个是因为一层会占用两行两列，如果是单数的，最后要将剩余的走完。所以最后还要做一次判断。因为每个元素访问一次，所以时间复杂度是O(m*n)，m，n是分别是矩阵的行数和列数，空间复杂度是O(1)。代码如下：

public ArrayList<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(matrix == null || matrix.length==0 || matrix[0].length==0)
        return res;
    int min = Math.min(matrix.length, matrix[0].length);
    int levelNum = min/2;
    for(int level=0;level<levelNum;level++)
    {
        for(int i=level;i<matrix[0].length-level-1;i++)
        {
            res.add(matrix[level][i]);
        }
        for(int i=level;i<matrix.length-level-1;i++)
        {
            res.add(matrix[i][matrix[0].length-1-level]);
        }
        for(int i=matrix[0].length-1-level;i>level;i--)
        {
            res.add(matrix[matrix.length-1-level][i]);
        }
        for(int i=matrix.length-1-level;i>level;i--)
        {
            res.add(matrix[i][level]);
        }
    }
    if(min%2==1)
    {
        if(matrix.length < matrix[0].length)
        {
            for(int i=levelNum; i<matrix[0].length-levelNum;i++)
            {
                res.add(matrix[levelNum][i]);
            }
        }
        else
        {
            for(int i=levelNum; i<matrix.length-levelNum;i++)
            {
                res.add(matrix[i][levelNum]);
            }
        }
    }
    return res;
}

因为这道题是比较简单的题目，所以上面提到的两个细节还是比较重要的，面试中遇到了一定要注意，尽量做到没有bug哈。

Anagrams -- LeetCode

原题链接: http://oj.leetcode.com/problems/anagrams/
这是一道很经典的面试题了，在cc150里面也有，就是把一个数组按照易位构词分类。易位构词其实也很好理解，就是两个单词所包含的字符和数量都是一样的，只是顺序不同。
这个题简单的版本是判断两个单词是不是anagram，一般来说有两种方法。第一种方法是用hashmap，key是字符，value是出现的次数，如果两个单词构成的hashmap相同，那么就是anagram。实现起来就是用一个构建hashmap，然后另一个在前面的hashmap中逐个去除，最后如果hashmap为空，即返回true。这个方法时间复杂度是O(m+n)，m，n分别是两个单词的长度。而空间复杂度是O(字符集的大小)。第二种方法是将两个单词排序，如果排序之后结果相同，就说明两个单词是anagram。这种方法的时间复杂度取决于排序算法，一般排序算法是O(nlogn)，如果字符集够小，也可以用线性的排序算法。不过总体来说，如果是判断两个单词的，第一种方法要直接简单一些。
接下来我们看看这道题，是在很多字符串里面按照anagram分类，如果用hashmap的方法，然后两两匹配，在分组会比较麻烦。而如果用排序的方法则有一个很大的优势，就是排序后的字符串可以作为一个key，也就是某一个class的id，如此只要对每一个字符串排序，然后建立一个hashmap，key是排序后的串，而value是所有属于这个key类的字符串，这样就可以比较简单的进行分类。假设我们有n个字符串，字符串最大长度是k，那么该算法的时间复杂度是O(nklogk)，其中O(klogk)是对每一个字符串排序（如果用线性算法也可以提高）。空间复杂度则是O(nk)，即hashmap的大小。实现代码如下：

public ArrayList<String> anagrams(String[] strs) {
    ArrayList<String> res = new ArrayList<String>();
    if(strs == null || strs.length == 0)
        return res;
    HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    for(int i=0;i<strs.length;i++)
    {
        char[] charArr = strs[i].toCharArray();
        Arrays.sort(charArr);
        String str = new String(charArr);
        if(map.containsKey(str))
        {
            map.get(str).add(strs[i]);
        }
        else
        {
            ArrayList<String> list = new ArrayList<String>();
            list.add(strs[i]);
            map.put(str,list);
        }
    }
    Iterator iter = map.values().iterator();
    while(iter.hasNext())
    {
        ArrayList<String> item = (ArrayList<String>)iter.next();
        if(item.size()>1)
            res.addAll(item);
    }
    return res;
}

理清了思路，实现起来还是比较简单的，这道题考察排序，hashmap，字符串处理，比较全面，在面试中非常常见，大家一定要熟悉哈。

Permutations II -- LeetCode

原题链接: http://oj.leetcode.com/problems/permutations-ii/
这个题跟Permutations非常类似，唯一的区别就是在这个题目中元素集合可以出现重复。这给我们带来一个问题就是如果不对重复元素加以区别，那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢？方法就是对于重复的元素循环时跳过递归函数的调用，只对第一个未被使用的进行递归，我们那么这一次结果会出现在第一个的递归函数结果中，而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归。想明白了这一点，代码其实很好修改。首先我们要对元素集合排序，从而让重复元素相邻，接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。代码如下：

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null && num.length==0)
        return res;
    Arrays.sort(num);
    helper(num, new boolean[num.length], new ArrayList<Integer>(), res);
    return res;
}
private void helper(int[] num, boolean[] used, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)
{
    if(item.size() == num.length)
    {
        res.add(new ArrayList<Integer>(item));
        return;
    }
    for(int i=0;i<num.length;i++)
    {
        if(i>0 && !used[i-1] && num[i]==num[i-1]) continue;
        if(!used[i])
        {
            used[i] = true;
            item.add(num[i]);
            helper(num, used, item, res);
            item.remove(item.size()-1);
            used[i] = false;
        }
    }
}

这样的解法是带有一般性的，把这个代码放到Permutations中也是正确的，所以如果熟悉的话，面试时如果碰到这个题目建议直接实现这个代码，不要假设元素没有重复，当然可以跟面试官讨论，不过一般来说都是要考虑这个情况的哈。

Permutations -- LeetCode

原题链接: http://oj.leetcode.com/problems/permutations/
这道题跟N-Queens，Sudoku Solver，Combination Sum，Combinations等一样，也是一个NP问题。方法还是原来那个套路，还是用一个循环递归处理子问题。区别是这里并不是一直往后推进的，前面的数有可能放到后面，所以我们需要维护一个used数组来表示该元素是否已经在当前结果中，因为每次我们取一个元素放入结果，然后递归剩下的元素，所以不会出现重复。时间复杂度还是NP问题的指数量级。代码如下：

public ArrayList<ArrayList<Integer>> permute(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null || num.length==0)
        return res;
    helper(num, new boolean[num.length], new ArrayList<Integer>(), res);
    return res;
}
private void helper(int[] num, boolean[] used, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)
{
    if(item.size() == num.length)
    {
        res.add(new ArrayList<Integer>(item));
        return;
    }
    for(int i=0;i<num.length;i++)
    {
        if(!used[i])
        {
            used[i] = true;
            item.add(num[i]);
            helper(num, used, item, res);
            item.remove(item.size()-1);
            used[i] = false;
        }
    }
}

注意在实现中有一个细节，就是在递归函数的前面，我们分别设置了used[i]的标记，表明改元素被使用，并且把元素加入到当前结果中，而在递归函数之后，我们把该元素从结果中移除，并把标记置为false，这个我们可以称为“保护现场”，递归函数必须保证在进入和离开函数的时候，变量的状态是一样的，这样才能保证正确性。当然也可以克隆一份结果放入递归中，但是那样会占用大量空间。所以个人认为这种做法是最高效的，而且这种方法在很多题目（几乎所有NP问题）中一直用到，不熟悉的朋友可以练习一下哈。
对于NP问题我们一直都是用递归方法，也是一个很成熟的套路，可以举一反三。不过有时候面试官会刻意让我们实现一下迭代的做饭，所以这里我们就介绍一下迭代的实现方法。迭代一般就是要理清每次加入一个新的元素，我们应该做什么，这里其实还是比较清晰的，假设有了当前前i个元素的所有permutation，当第i+1个元素加进来时，我们要做的就是将这个元素带入每一个之前的结果，并且放到每一个结果的各个位置中。因为之前的结果没有重复，所以带入新元素之后也不会有重复（当然这里假设数字集合本身是没有重复的元素的）。按照这个思路，实现的代码如下：

public ArrayList<ArrayList<Integer>> permute(int[] num) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num == null || num.length==0)
        return res;
    ArrayList<Integer> first = new ArrayList<Integer>();
    first.add(num[0]);
    res.add(first);
    for(int i=1;i<num.length;i++)
    {
        ArrayList<ArrayList<Integer>> newRes = new ArrayList<ArrayList<Integer>>();
        for(int j=0;j<res.size();j++)
        {
            ArrayList<Integer> cur = res.get(j);
            for(int k=0;k<cur.size()+1;k++)
            {
                ArrayList<Integer> item = new ArrayList<Integer>(cur);
                item.add(k,num[i]);
                newRes.add(item);
            }
        }
        res = newRes;
    }
    return res;   
}

上面的代码有时候乍一看可能觉得只有两层循环，时间复杂度是不是O(n^2)之类的。事实上肯定不是的，因为注意第二层循环是对于res进行遍历的，而res是一直在以平方量级增长的，所以总的时间复杂度还是会是指数量级以上的。
这种NP问题的求解在LeetCode中非常常见，类似的有N-Queens，Sudoku Solver，Combination Sum，Combinations，不过思路差不多，掌握套路就不难了。这道题还有一个扩展就是如果元素集合中会出现重复，那么意味着我们需要跳过一些重复元素，具体的细节可以参见Permutations II。

Rotate Image -- LeetCode

原题链接: http://oj.leetcode.com/problems/rotate-image/
这道题虽然操作起来有一点繁琐，但是思路比较简单，就是考察一下数组的基本操作。基本思路是把图片分为行数/2层，然后一层层进行旋转，每一层有上下左右四个列，然后目标就是把上列放到右列，右列放到下列，下列放到左列，左列放回上列，中间保存一个临时变量即可。因为每个元素搬运的次数不会超过一次，时间复杂度是O(矩阵的大小)，空间复杂度是O(1)。代码如下：

public void rotate(int[][] matrix) {
    if(matrix == null || matrix.length==0 || matrix[0].length==0)
        return;
    int layerNum = matrix.length/2;
    for(int layer=0;layer<layerNum;layer++)
    {
        for(int i=layer;i<matrix.length-layer-1;i++)
        {
            int temp = matrix[layer][i];
            matrix[layer][i] = matrix[matrix.length-1-i][layer];
            matrix[matrix.length-1-i][layer] = matrix[matrix.length-1-layer][matrix.length-1-i];
            matrix[matrix.length-1-layer][matrix.length-1-i] = matrix[i][matrix.length-1-layer];
            matrix[i][matrix.length-1-layer] = temp;
        }
    }
}

这种题目就是思路比较简单，不过实现的时候要细心，容易出错。如果面试遇到了还得谨慎对待，尽量不要出错哈。

Reorder List -- LeetCode

原题链接: http://oj.leetcode.com/problems/reorder-list/
这是一道比较综合的链表操作的题目，要按照题目要求给链表重新连接成要求的结果。其实理清思路也比较简单，分三步完成：（1）将链表切成两半，也就是找到中点，然后截成两条链表；（2）将后面一条链表进行reverse操作，就是反转过来；（3）将两条链表按顺序依次merge起来。
这几个操作都是我们曾经接触过的操作了，第一步找中点就是用Linked List Cycle中的walker-runner方法，一个两倍速跑，一个一倍速跑，知道快的碰到链表尾部，慢的就正好停在中点了。第二步是比较常见的reverse操作，在Reverse Nodes in k-Group也有用到了，一般就是一个个的翻转过来即可。第三步是一个merge操作，做法类似于Sort List中的merge，只是这里不需要比较元素打小了，只要按顺序左边取一个，右边取一个就可以了。
接下来看看时间复杂度，第一步扫描链表一遍，是O(n)，第二步对半条链表做一次反转，也是O(n)，第三部对两条半链表进行合并，也是一遍O(n)。所以总的时间复杂度还是O(n)，由于过程中没有用到额外空间，所以空间复杂度O(1)。代码如下：

public void reorderList(ListNode head) {
    if(head == null || head.next==null)
    {
        return;
    }
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null)
    {
        walker = walker.next;
        runner = runner.next.next;
    }
    ListNode head1 = head;
    ListNode head2 = walker.next;
    walker.next = null;
    head2 = reverse(head2);
    while(head1!=null && head2!=null)
    {
        ListNode next = head2.next;
        head2.next = head1.next;
        head1.next = head2;
        head1 = head2.next;
        head2 = next;
    }
}
private ListNode reverse(ListNode head)
{
    ListNode pre = null;
    ListNode cur = head;
    while(cur!=null)
    {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

这道题看起来比较复杂，其实理清思路之后就都是链表常见的几个基本操作。这里我想多说一下reverse操作，因为这是链表最常见的操作。有时候在第一轮电面这种比较基础的面试中，可能会要求实现reverse操作，但是因为有点过于简单，面试官会要求递归和非递归都实现一下。上面的代码使用非递归的方式实现reverse。下面我们列举一下递归的代码，有兴趣的朋友可以看看哈。

public ListNode recursive_reverse(ListNode head) {
    if(head == null || head.next==null)
        return head;
    return recursive_reverse(head, head.next);
}
private ListNode recursive_reverse(ListNode current, ListNode next) 
{
    if (next == null) return current;
    ListNode newHead = recursive_reverse(current.next, next.next);
    next.next = current;
    current.next = null;
    return newHead;
}

Binary Tree Preorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-preorder-traversal/
跟Binary Tree Inorder Traversal一样，二叉树的先序遍历我们仍然介绍三种方法，第一种是递归，第二种是迭代方法，第三种是用线索二叉树。
递归是最简单的方法，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。代码如下：

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    helper(root, res);
    return res;
}
private void helper(TreeNode root, ArrayList<Integer> res)
{
    if(root == null)
        return;
    res.add(root.val);
    helper(root.left,res);
    helper(root.right,res);
}

接下来是迭代的做法，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。实现的代码如下：

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    while(root!=null || !stack.isEmpty())
    {
        if(root!=null)
        {
            stack.push(root);
            res.add(root.val);
            root = root.left;
        }
        else
        {
            root = stack.pop();
            root = root.right;
        }
    }
    return res;
}

最后使用Morris遍历方法，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。具体的分析可以参见Binary Tree Inorder Traversal，中序和先序方法上是完全一样的，只是访问结点的时机不同而已。这种方法的缺陷在于会暂时性的改变结点的内容，从编程健壮性和封装性来说不是特别好（比如说传进来的树结点很可能是const的变量，不希望对它做任何改变）。时间复杂度和空间复杂度如同Binary Tree Inorder Traversal中分析的，分别是O(n)和O(1)。代码如下：

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    TreeNode cur = root;
    TreeNode pre = null;
    while(cur != null)
    {
        if(cur.left == null)
        {
            res.add(cur.val);
            cur = cur.right;
        }
        else
        {
            pre = cur.left;
            while(pre.right!=null && pre.right!=cur)
                pre = pre.right;
            if(pre.right==null)
            {
                res.add(cur.val);
                pre.right = cur;
                cur = cur.left;
            }
            else
            {
                pre.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

上面介绍了三种方法来实现树的先序遍历，这种题目看上去很简单，但是大家还是不能满足于递归的方法，有些onsite面试还是会在简单问题上要求很高的。

Candy -- LeetCode

原题链接: http://oj.leetcode.com/problems/candy/
这道题用到的思路和Trapping Rain Water是一样的，用动态规划。基本思路就是进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个小孩左边所需要最少的糖果数量，存入数组对应元素中，第二次扫描的时候维护右边所需的最少糖果数，并且比较将左边和右边大的糖果数量存入结果数组对应元素中。这样两遍扫描之后就可以得到每一个所需要的最最少糖果量，从而累加得出结果。方法只需要两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组，复杂度是O(n)。代码如下：

public int candy(int[] ratings) {
    if(ratings==null || ratings.length==0)
    {
        return 0;
    }
    int[] nums = new int[ratings.length];
    nums[0]=1;
    
    for(int i=1;i<ratings.length;i++)
    {
        if(ratings[i]>ratings[i-1])
        {
            nums[i] = nums[i-1]+1;
        }
        else
        {
            nums[i] = 1;
        }
    }
    int res = nums[ratings.length-1];
    for(int i=ratings.length-2;i>=0;i--)
    {
        int cur = 1;
        if(ratings[i]>ratings[i+1])
        {
            cur = nums[i+1]+1;
        }
        res += Math.max(cur,nums[i]);
        nums[i] = cur;
    }
    return res;
}

这种两边扫描的方法是一种比较常用的技巧，LeetCode中Trapping Rain Water和这道题都用到了，可以把这种方法作为自己思路的一部分，通常是要求的变量跟左右元素有关系的题目会用到哈。

Jump Game II -- LeetCode

原题链接: http://oj.leetcode.com/problems/jump-game-ii/
这道题是Jump Game的扩展，区别是这道题不仅要看能不能到达终点，而且要求到达终点的最少步数。其实思路和Jump Game还是类似的，只是原来的全局最优现在要分成step步最优和step-1步最优（假设当前步数是step）。当走到超过step-1步最远的位置时，说明step-1不能到达当前一步，我们就可以更新步数，将step+1。时间复杂度仍然是O(n)，空间复杂度也是O(1)。代码如下：

public int jump(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int lastReach = 0;
    int reach = 0;
    int step = 0;
    for(int i=0;i<=reach&&i<A.length;i++)
    {
        if(i>lastReach)
        {
            step++;
            lastReach = reach;
        }
        reach = Math.max(reach,A[i]+i);
    }
    if(reach<A.length-1)
        return 0;
    return step;
}

动态规划是面试中特别是onsite中非常重要的类型，一般面试中模型不会过于复杂，所以大家可以熟悉一下比较经典的几个题，比如Jump Game，Maximum Subarray等。

Jump Game -- LeetCode

原题链接: http://oj.leetcode.com/problems/jump-game/
这道题是动态规划的题目，所用到的方法跟是在Maximum Subarray中介绍的套路，用“局部最优和全局最优解法”。我们维护一个到目前为止能跳到的最远距离，以及从当前一步出发能跳到的最远距离。局部最优local=A[i]+i，而全局最优则是global=Math.max(global, local)。递推式出来了，代码就比较容易实现了。因为只需要一次遍历时间复杂度是O(n)，而空间上是O(1)。代码如下：

public boolean canJump(int[] A) {
    if(A==null || A.length==0)
        return false;
    int reach = 0;
    for(int i=0;i<=reach&&i<A.length;i++)
    {
        reach = Math.max(A[i]+i,reach);
    }
    if(reach<A.length-1)
        return false;
    return true;
}

这也是一道比较经典的动态规划的题目，不过不同的切入点可能会得到不同复杂度的算法，比如如果维护的历史信息是某一步是否能够到达，那么每一次需要维护当前变量的时候就需要遍历前面的所有元素，那么总的时间复杂度就会是O(n^2)。所以同样是动态规划，有时候也会有不同的角度，不同效率的解法。这道题目还有一个扩展Jump Game II，有兴趣的朋友可以看看。

Maximum Subarray -- LeetCode

原题链接: http://oj.leetcode.com/problems/maximum-subarray/
这是一道非常经典的动态规划的题目，用到的思路我们在别的动态规划题目中也很常用，以后我们称为”局部最优和全局最优解法“。
基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第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])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。

接下来我们分析一下复杂度，时间上只需要扫描一次数组，所以时间复杂度是O(n)。空间上我们可以看出表达式中只需要用到上一步local[i]和global[i]就可以得到下一步的结果，所以我们在实现中可以用一个变量来迭代这个结果，不需要是一个数组，也就是如程序中实现的那样，所以空间复杂度是两个变量（local和global），即O(2)=O(1)。
代码如下：

public int maxSubArray(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int global = A[0];
    int local = A[0];
    for(int i=1;i<A.length;i++)
    {
        local = Math.max(A[i],local+A[i]);
        global = Math.max(local,global);
    }
    return global;
}

这道题虽然比较简单，但是用到的动态规划方法非常的典型，我们在以后的题目中还会遇到，大家还是要深入理解一下哈。我现在记得的用到的题目是Jump Game，以后有统计一下再继续更新。

LRU Cache -- LeetCode

原题链接: http://oj.leetcode.com/problems/lru-cache/
这是一道非常综合的题目，主要应用在操作系统的资源管理中。
按照题目要求，要实现get和set功能，为了满足随机存储的需求我们首先想到的一般是用数组，如果用链表会有O(n)的访问时间。然而他又有另一个条件就是要维护least used的队列，也就是说经常用的放在前面，用的少的放在后面。这样当资源超过cache的容积的时候就可以把用得最少的资源删掉。这就要求我们要对节点有好的删除和插入操作，这个要求又会让我们想到用链表，因为数组的删除和插入是O(n)复杂度的。
那么我们能不能维护一个数据结构使得访问操作和插入删除操作都是O(1)复杂度的呢？答案是肯定的。这个数据结构比较复杂，是用一个hash表加上一个双向链表来实现。基本思路是这样的，用一个hash表来维护结点的位置关系，也就是hash表的key就是资源本身的key，value是资源的结点（包含key和value的信息）。然后把结点维护成一个双向链表构成的队列，这样子如果我们要访问某一个结点，那么可以通过hash表和key来找到结点，从而取到相应的value。而当我们想要删除或者插入结点时，我们还是通过hash表找到结点，然后通过双向链表和队列的尾结点把自己删除同时插入到队尾。通过hash表访问结点我们可以认为是O(1)的操作（假设hash函数足够好），然后双向链表的插入删除操作也是O(1)的操作。如此我们便实现了用O(1)时间来完成所有LRU cache的操作。空间上就是对于每一个资源有一个hash表的的项以及一个对应的结点（包含前后指针和资源的<key, value>）。代码如下：

public class LRUCache {
    class Node
    {
        Node pre, next;
        int key;
        int val;
        public Node(int key, int value)
        {
            this.key = key;
            this.val = value;
        }
    }
    
    private int capacity;
    private int num;
    private HashMap<Integer, Node> map;
    private Node first, last;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        num = 0;
        map = new HashMap<Integer, Node>();
        first = null;
        last = null;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null)
            return -1;
        else if(node!=last)
        {
            if(node == first)
                first = first.next;
            else
                node.pre.next = node.next;
            node.next.pre = node.pre;
            last.next = node;
            node.pre = last;
            node.next = null;
            last = node;
        }
        return node.val;
    }
    
    public void set(int key, int value) {
        Node node = map.get(key);
        if(node != null)
        {
            node.val = value;
            if(node!=last)
            {
                if(node == first)
                    first = first.next;
                else
                    node.pre.next = node.next;
                node.next.pre = node.pre;
                last.next = node;
                node.pre = last;
                node.next = null;
                last = node;
            }
        }
        else 
        {
            Node newNode = new Node(key,value);

            if(num>=capacity)
            {
                map.remove(first.key);
                first = first.next;
                if(first!=null)
                    first.pre = null;
                else
                    last = null;
                num--;    
            }
            if(first == null || last == null)
            {
                first = newNode;
            }
            else
            {
                last.next = newNode;
            }
            newNode.pre = last;
            last = newNode;
            map.put(key,newNode);
            num++;
        }

    }
}

实现的时候还是有很多细节的，因为我们不经常使用双向链表，插入删除操作要维护前后指针，并且同时要维护成队列，增加了许多注意点。这道题是一道很实际的题目，思路和数据结构都是很适合面试的题目，但是代码量有些偏大，所以一般只在onsite的时候有可能遇到，可能也不会让你完整地写出全部代码，主要还是讲出维护的数据结构和各种操作复杂度的分析。

Linked List Cycle II -- LeetCode

原题链接: http://oj.leetcode.com/problems/linked-list-cycle-ii/
这道题是Linked List Cycle的扩展，就是在确定是否有cycle之后还要返回cycle的起始点的位置。从Linked List Cycle中用的方法我们可以得知a=kc-b（不了解的朋友可以先看看Linked List Cycle）。现在假设有两个结点，一个从链表头出发，一个从b点出发，经过a步之后，第一个结点会到达cycle的出发点，而第二个结点会走过kc-b，加上原来的b刚好也会停在cycle的起始点。如此我们就可以设立两个指针，以相同速度前进知道相遇，而相遇点就是cycle的起始点。算法的时间复杂度是O(n+a)=O(2n)=O(n)，先走一次确定cycle的存在性并且走到b点，然后走a步找到cycle的起始点。空间复杂度仍是O(1)。代码如下：

public ListNode detectCycle(ListNode head)
{
    if(head == null || head.next == null)
        return null;
    ListNode walker = head.next;
    ListNode runner = head.next.next;
    while(runner!=null && walker!=runner)
    {
        walker = walker.next;
        if(runner.next!=null)
            runner = runner.next.next;
        else
            runner = null;
    }
    if(runner == null)
        return null;
    runner = head;
    while(walker!=runner)
    {
        walker = walker.next;
        runner = runner.next;
    }
    return walker;
}

这道题目更多的是数学上相遇点的推导，有了理论基础之后就是比较简单的链表操作。

Combinations -- LeetCode

原题链接: http://oj.leetcode.com/problems/combinations/
这道题是NP问题的题目，时间复杂度没办法提高，用到的还是N-Queens中的方法：用一个循环递归处理子问题。实现的代码跟Combination Sum非常类似而且更加简练，因为不用考虑重复元素的情况，而且元素只要到了k个就可以返回一个结果。代码如下：

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(n<=0 || n<k)
        return res;
    helper(n,k,1,new ArrayList<Integer>(), res);
    return res;
}
private void helper(int n, int k, int start, ArrayList<Integer> item, ArrayList<ArrayList<Integer>> res)
{
    if(item.size()==k)
    {
        res.add(new ArrayList<Integer>(item));
        return;
    }
    for(int i=start;i<=n;i++)
    {
        item.add(i);
        helper(n,k,i+1,item,res);
        item.remove(item.size()-1);
    }
}

NP问题在LeetCode中出现的频率很高，例如N-Queens，Sudoku Solver，Combination Sum，Permutations等等。不过这类题目都是用一种方法而且也没有办法有时间上的提高，所以还是比较好掌握的。

Linked List Cycle -- LeetCode

原题链接: http://oj.leetcode.com/problems/linked-list-cycle/
这道题是cc150里面的题目，算是链表里面比较经典的题目。
我们先讲一下比较直接容易想到的方法，就是用一个hashset，然后把扫过的结点放入hashset中，如果出现重复则返回true。想法比较简单，也很好实现，这里就不放代码了，有兴趣的朋友可以写写。
下面我们来考虑如何不用额外空间来判断是否有cycle，用到的方法很典型，就是那种walker-runner的方法，基本想法就是维护两个指针，一个走的快，一个走得慢，当一个走到链表尾或者两个相见的时候，能得到某个想要的结点，比如相遇点，中点等等。
介绍完方法，剩下的主要就是数学了，假设两个指针walker和runner，walker一倍速移动，runner两倍速移动。有一个链表，假设他在cycle开始前有a个结点，cycle长度是c，而我们相遇的点在cycle开始后b个结点。那么想要两个指针相遇，意味着要满足以下条件：(1) a+b+mc=s; (2) a+b+nc=2s; 其中s是指针走过的步数，m和n是两个常数。这里面还有一个隐含的条件，就是s必须大于等于a，否则还没走到cycle里面，两个指针不可能相遇。假设k是最小的整数使得a<=kc，也就是说(3) a<=kc<=a+c。接下来我们取m=0, n=k，用(2)-(1)可以得到s=kc以及a+b=kc。由此我们可以知道，只要取b=kc-a(由(3)可以知道b不会超过c)，那么(1)和(2)便可以同时满足，使得两个指针相遇在离cycle起始点b的结点上。
因为s=kc<=a+c=n，其中n是链表的长度，所以走过的步数小于等于n，时间复杂度是O(n)。并且不需要额外空间，空间复杂度O(1)。代码如下：

public boolean hasCycle(ListNode head) {
    if(head == null)
        return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner!=null && runner.next!=null)
    {
        walker = walker.next;
        runner = runner.next.next;
        if(walker == runner)
            return true;
    }
    return false;
}

这道题是链表中比较有意思的题目，基于这个方法，我们不仅可以判断链表中有没有cycle，还可以确定cycle的位置，有兴趣的朋友可以看看Linked List Cycle II。

Wildcard Matching -- LeetCode

原题链接: http://oj.leetcode.com/problems/wildcard-matching/
这道题目其实是Regular Expression Matching的简化版，在这里'?'相当于那边的'.'，而'*'相当于那边的'.*'，因为这里'*'就可以代替任何字符串，不需要看前面的字符，所以处理起来更加简单。
brute force的方法就不重新列举代码了，有兴趣实现的朋友可以参考一下Regular Expression Matching，代码结构一样，只是处理情况变一下就可以，不过leetcode过不了（因为超时）。
我们主要还是说一下动态规划的方法。跟Regular Expression Matching一样，还是维护一个假设我们维护一个布尔数组res[i],代表s的前i个字符和p的前j个字符是否匹配(这里因为每次i的结果只依赖于j-1的结果，所以不需要二维数组，只需要一个一维数组来保存上一行结果即可），递推公式分两种情况：
    (1)p[j]不是'*'。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是'?'，也是相同），并且res[i]==true，则更新res[i+1]为true，否则res[i+1]=false; 
    (2)p[j]是'*'。因为'*'可以匹配任意字符串，所以在前面的res[i]只要有true，那么剩下的          res[i+1], res[i+2],...,res[s.length()]就都是true了。
算法的时间复杂度因为是两层循环，所以是O(m*n), 而空间复杂度只用一个一维数组，所以是O(n)，假设s的长度是n，p的长度是m。代码如下：

public boolean isMatch(String s, String p) {
    if(p.length()==0)
        return s.length()==0;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int j=0;j<p.length();j++)
    {
        if(p.charAt(j)!='*')
        {
            for(int i=s.length()-1;i>=0;i--)
            {
                res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));
            }
        }
        else
        {
            int i = 0;
            while(i<=s.length() && !res[i])
                i++;
            for(;i<=s.length();i++)
            {
                res[i] = true;
            }
        }
        res[0] = res[0]&&p.charAt(j)=='*';
    }
    return res[s.length()];
}

这里有个问题，就是如果把以上代码直接放到LeetCode中去测试，会有最后一个test case过不了，说超时了，这道题的AC率这么低就是因为这个case，从难度来说，这个题比Regular Expression Matching简单一些。个人觉得这其实是LeetCode的问题，把测试超时的槛设得太低了，好像用C++就能过，因为效率比较高，而java可能要抠各种细节，这其实意义不是很大，既然算法复杂度已经到位了，就应该可以过，甚至觉得时间应该设得更高一些，连同brute force也让过，这样方便大家测试一道题的不同解法，至少检验正确性，时间上大家自己去分析就可以。所以如果想要过最后一个case可以在代码的第一个if以后加上以下两行跳过那个case：

if(s.length()>300 && p.charAt(0)=='*' && p.charAt(p.length()-1)=='*')
    return false;

这种模糊匹配的题目是面试中的一类题目，一般在onsite的时候会遇到，如果没有熟悉思路有时候当场可能很难做得很好。

Insertion Sort List -- LeetCode

原题链接: http://oj.leetcode.com/problems/insertion-sort-list/
这道题跟Sort List类似，要求在链表上实现一种排序算法，这道题是指定实现插入排序。插入排序是一种O(n^2)复杂度的算法，基本想法相信大家都比较了解，就是每次循环找到一个元素在当前排好的结果中相对应的位置，然后插进去，经过n次迭代之后就得到排好序的结果了。了解了思路之后就是链表的基本操作了，搜索并进行相应的插入。时间复杂度是排序算法的O(n^2)，空间复杂度是O(1)。代码如下：

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

这道题其实主要考察链表的基本操作，用到的小技巧也就是在Swap Nodes in Pairs中提到的用一个辅助指针来做表头避免处理改变head的时候的边界情况。作为基础大家还是得练习一下哈。

Sort List -- LeetCode

原题链接: http://oj.leetcode.com/problems/sort-list/
这道题跟Insertion Sort List类似，要求我们用O(nlogn)算法对链表进行排序，但是并没有要求用哪一种排序算法，我们可以使用归并排序，快速排序，堆排序等满足要求的方法来实现。对于这道题比较容易想到的是归并排序，因为我们已经做过Merge Two Sorted Lists，这是归并排序的一个subroutine。剩下我们需要做的就是每次找到中点，然后对于左右进行递归，最后用Merge Two Sorted Lists把他们合并起来。代码如下：

public ListNode sortList(ListNode head) {
    return mergeSort(head);
}
private ListNode mergeSort(ListNode head)
{
    if(head == null || head.next == null)
        return head;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null)
    {
        walker = walker.next;
        runner = runner.next.next;
    }
    ListNode head2 = walker.next;
    walker.next = null;
    ListNode head1 = head;
    head1 = mergeSort(head1);
    head2 = mergeSort(head2);
    return merge(head1, head2);
}
private ListNode merge(ListNode head1, ListNode head2)
{
    ListNode helper = new ListNode(0);
    helper.next = head1;
    ListNode pre = helper;
    while(head1!=null && head2!=null)
    {
        if(head1.val<head2.val)
        {
            head1 = head1.next;
        }
        else
        {
            ListNode next = head2.next;
            head2.next = pre.next;
            pre.next = head2;
            head2 = next;
        }
        pre = pre.next;
    }
    if(head2!=null)
    {
        pre.next = head2;
    }
    return helper.next;
}

不过用归并排序有个问题就是这里如果把栈空间算上的话还是需要O(logn)的空间的。对于其他排序算法，用兴趣的同学可以实现一下哈。
排序是面试中比较基础的一个主题，所以对于各种常见的排序算法大家还是要熟悉，不了解的朋友可以参见排序算法 - Wiki。特别是算法的原理，很多题目虽然没有直接考察排序的实现，但是用到了其中的思想，比如非常经典的topK问题，就用到了快速排序的原理，关于这个问题在Median of Two Sorted Arrays中有提到，有兴趣的朋友可以看看。

Max Points on a Line -- LeetCode

原题链接: http://oj.leetcode.com/problems/max-points-on-a-line/
这道题属于计算几何的题目，要求给定一个点集合，是求出最多点通过一条直线的数量。我的思路是n个点总共构成n*(n-1)/2条直线，然后对每条直线看看是有多少点在直线上，记录下最大的那个，最后返回结果。而判断一个点p_k在p_i, p_j构成的直线上的条件是(p_k.y-p_i.y)*(p_j.x-p_i.x)==(p_j.y-p_i.y)*(p_k.x-p_i.x)。算法总共是三层循环，时间复杂度是O(n^3),空间复杂度则是O(1),因为不需要额外空间做存储。代码如下：

public int maxPoints(Point[] points) {
    if(points==null || points.length==0)
    {
        return 0;
    }
    if(allSamePoints(points))
        return points.length;
    int max = 0;
    for(int i=0;i<points.length-1;i++)
    {
        for(int j=i+1;j<points.length;j++)
        {
            if(points[j].y==points[i].y && points[j].x==points[i].x)
                continue;
            int cur = 2;
            for(int k=0;k<points.length;k++)
            {
                if(k!=i && k!=j 
                && (points[k].y-points[i].y)*(points[j].x-points[i].x)
                    ==(points[j].y-points[i].y)*(points[k].x-points[i].x))
                    cur++;
            }
            max = Math.max(max,cur);
        }
    }
    return max;
}
private boolean allSamePoints(Point[] points)
{
    for(int i=1;i<points.length;i++)
    {
        if(points[0].y!=points[i].y || points[0].x!=points[i].x)
            return false;
    }
    return true;
}

大家看到代码中还写了一个allSamePoints的函数，这是一个非常corner的情况，就是所有点都是一个点的情况，因为下面我们要跳过重复的点（否则两个重合点会认为任何点都在他们构成的直线上），但是偏偏当所有点都重合时，我们需要返回所有点。除了这种情况，只要有一个点不重合，我们就会从那个点得到结果，这是属于比较tricky的情况。
经过一个朋友的提醒， 这道题还可以有另一种做法， 基本思路是这样的， 每次迭代以某一个点为基准， 看后面每一个点跟它构成的直线， 维护一个HashMap， key是跟这个点构成直线的斜率的值， 而value就是该斜率对应的点的数量， 计算它的斜率， 如果已经存在， 那么就多添加一个点， 否则创建新的key。 这里只需要考虑斜率而不用考虑截距是因为所有点都是对应于一个参考点构成的直线， 只要斜率相同就必然在同一直线上。 最后取map中最大的值， 就是通过这个点的所有直线上最多的点的数量。 对于每一个点都做一次这种计算， 并且后面的点不需要看扫描过的点的情况了， 因为如果这条直线是包含最多点的直线并且包含前面的点， 那么前面的点肯定统计过这条直线了。 因此算法总共需要两层循环， 外层进行点的迭代， 内层扫描剩下的点进行统计， 时间复杂度是O（n^2), 空间复杂度是哈希表的大小， 也就是O（n), 比起上一种做法用这里用哈希表空间省去了一个量级的时间复杂度。 代码如下：

public int maxPoints(Point[] points) {
    if (points == null || points.length == 0) return 0;
    int max = 1;
    double ratio = 0.0;
    for (int i = 0; i < points.length - 1; i++) 
    {
        HashMap<Double, Integer> map = new HashMap<Double, Integer>();
        int numofSame = 0;
        int localMax = 1;
        for (int j = i + 1; j < points.length; j++) 
        {
            if(points[j].x == points[i].x && points[j].y == points[i].y) {
                numofSame++;
                continue;
            }
            else if(points[j].x == points[i].x)
            {
                ratio = (double) Integer.MAX_VALUE;
            }
            else if(points[j].y == points[i].y)
            {
                ratio = 0.0;
            }
            else
            {
                ratio = (double) (points[j].y - points[i].y) / (double) (points[j].x - points[i].x);
            }
            if (map.containsKey(ratio)) 
            {
                int num = map.get(ratio);
                map.put(ratio, num + 1);
            }
            else 
            {
                map.put(ratio, 2);
            }
        }
        for (Integer value : map.values()) 
        {
            localMax = Math.max(localMax, value);
        }
        localMax += numofSame;
        max = Math.max(max, localMax);
    }
    return max;
}

计算几何的题目在现在的面试中挺常见的，可能因为有些问题比较实用的缘故，而且实现中一般细节比较多，容易出bug，所以还是得重视。如果有朋友有更好的解法或者思路，欢迎交流哈，可以留言或者发邮件到linhuanmars@gmail.com给我。

Evaluate Reverse Polish Notation -- LeetCode

原题链接: http://oj.leetcode.com/problems/evaluate-reverse-polish-notation/
这道题是逆波兰式的求解，不了解逆波兰式的朋友可以参考一下逆波兰表示法 - wiki。逆波兰式有个优点就是他不需要括号来表示优先级，直接根据式子本身就可以求解。思路是维护一个运算数栈，读到运算数的时候直接进栈，而每得到一个运算符，就从栈顶取出两个运算数，运算之后将结果做为一个运算数放回栈中，直到式子结束，此时栈中唯一一个元素便是结果。代码如下：

public int evalRPN(String[] tokens) {
    if(tokens==null || tokens.length==0)
        return 0;
    LinkedList<Integer> stack = new LinkedList<Integer>();
    for(int i=0;i<tokens.length;i++)
    {
        if(tokens[i].equals("+"))
        {
            stack.push(stack.pop()+stack.pop());
        }
        else if(tokens[i].equals("-"))
        {
            stack.push(-stack.pop()+stack.pop());
        }
        else if(tokens[i].equals("*"))
        {
            stack.push(stack.pop()*stack.pop());
        }
        else if(tokens[i].equals("/"))
        {
            int num1 = stack.pop();
            int num2 = stack.pop();
            stack.push(num2/num1);
        }
        else
        {
            stack.push(Integer.parseInt(tokens[i]));
        }
    }
    return stack.pop();
}

以上代码中有一个没有周全的地方是没有对逆波兰式错误的情况进行出错处理，其实也不难，就是每次pop操作检查栈空情况，如果栈空，则说明出错。还有就是最后检查一下栈的size，如果不是1也说明运算数多了，返回错误。有兴趣的朋友可以自己补充一下哈。
和这道题类似的，有波兰式求解，中缀表达式求解，这几个其实是表达式的不同表达方式。既然这里出现了逆波兰式，大家还是看看其他两种的求解方法，原理其实近似，都是通过维护栈来实现，网上也有不少材料，这里就不细说了。

Reverse Words in a String -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-words-in-a-string/
这道题是字符串处理的题目，我们先介绍一种很直接的做法，就是类似于java中String::split函数做的操作，把字符串按空格分开，不过我们把重复的空格直接忽略过去。接下来就是把得到的结果单词反转过来得到结果。因为过程中就是一次扫描得到字符串，然后再一次扫描得出结果，所以时间复杂度是O(n)。空间上要用一个数组来存，所以是O(n)。实现思路比较清晰，这里就不列举迭代实现的代码了，有兴趣的朋友可以练习一下哈。下面的代码是这种方法的递归实现：

public String reverseWords(String s) {
    s = s.trim();
    return helper(s,0).toString();
}
private StringBuilder helper(String s, int index)
{
    if(index>=s.length())
        return new StringBuilder(); 
    StringBuilder cur = new StringBuilder();
    int lastIndex = index;
    while(index < s.length() && s.charAt(index)!=' ')
    {
        cur.append(s.charAt(index++));
    }
    while(index < s.length() && s.charAt(index)==' ')
        index++;
    if(lastIndex == 0)
        return helper(s,index).append(cur);
    return helper(s,index).append(cur).append(' ');
}

接下来我们再介绍另一种方法，思路是先把整个串反转并且同时去掉多余的空格，然后再对反转后的字符串对其中的每个单词进行反转，比如"the sky is blue"，先反转成"eulb si yks eht"，然后在对每一个单词反转，得到"blue is sky the"。这种方法先反转的时间复杂度是O(n)，然后再对每个单词反转需要扫描两次（一次是得到单词长度，一次反转单词）,所以总复杂度也是O(n)，比起上一种方法并没有提高，甚至还多扫描了一次，不过空间上这个不需要额外的存储一份字符串，不过从量级来说也还是O(n)。代码如下：

public String reverseWords(String s) {
    if(s==null) return null;
    s = s.trim();
    if(s.length()==0) return "";
    StringBuilder res = new StringBuilder();
    for(int i=s.length()-1; i>=0; i--){
        if(i!=s.length()-1 && s.charAt(i)==' ' && s.charAt(i)==s.charAt(i+1)) continue;
        res.append(s.charAt(i));
    }
    int left=0;
    int right=0;
    while(right<res.length()){
        while(right<res.length() && res.charAt(right)!=' '){
     right++;
        }
        int next = right+1;
        right--;
        while(left<right){
            char temp = res.charAt(left);
            res.setCharAt(left++, res.charAt(right));
            res.setCharAt(right--, temp);
        }
        left = next;
        right = next;
    }
    return res.toString();
}

Multiply Strings -- LeetCode

原题链接: http://oj.leetcode.com/problems/multiply-strings/
这道题属于数值操作的题目，其实更多地是考察乘法运算的本质。基本思路是和加法运算还是近似的，只是进位和结果长度复杂一些。我们仍然是从低位到高位对每一位进行计算，假设第一个数长度是n，第二个数长度是m，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。对于某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，即第1位和第i位，第2位和第i-1位，... ，然后累加起来，最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。这个算法两层循环，每层循环次数是O(m+n)，所以时间复杂度是O((m+n)^2)。算法中不需要额外空间，只需要维护一个进位变量即可，所以空间复杂度是O(1)。代码如下：

public String multiply(String num1, String num2) {
    if(num1 == null || num2 == null || num1.length()==0 || num2.length()==0)
        return "";
    if(num1.charAt(0)=='0')
        return "0";
    if(num2.charAt(0)=='0')
        return "0";
    StringBuilder res = new StringBuilder();
    int num = 0;
    for(int i=num1.length()+num2.length();i>0;i--)
    {
        for(int j=Math.min(i-1,num1.length());j>0;j--)
        {
            if(i-j<=num2.length())
            {
                num += (int)(num1.charAt(j-1)-'0')*(int)(num2.charAt(i-1-j)-'0');
            }
        }
        if(i!=1 || num>0)
            res.append(num%10);
        num = num/10;
    }
    return res.reverse().toString();
}

实现中有两个小细节，一个是循环中最后有一个if判断，其实就是看最高一位是不是0（最高第二位不可能是0，除非两个源字符串最高位带有0），如果是就不需要加入字符串中了。另一个小问题是我们是由低位到高位放入结果串的，所以最后要进行一次reverse，因为是一个O(m+n)的操作，不会影响算法复杂度。
这道题其实还有更加优的做法，就是用十大最牛的算法之一--Fast Fourier transform(FFT)。使用FFT可以在O(nlogn)时间内求出多项式的乘法，在这里只需要把变量x带入10，然后按照求多项式的方法就可以求出两个大整数的成绩了。想了解细节的朋友搜一下快速傅里叶变换求多项式乘积就可以找到相关资料了，是比较成熟的算法。不过FFT实现不是很简单，所以在面试中一般不需要写代码，只需要知道这个思路和基本工作原理就可以了哈。

Trapping Rain Water -- LeetCode

原题链接: http://oj.leetcode.com/problems/trapping-rain-water/
这道题比较直接的做法类似Longest Palindromic Substring中的第一种方法，对于每一个bar往两边扫描，找到它能承受的最大水量，然后累加起来即可。每次往两边扫的复杂度是O(n)，对于每个bar进行处理，所以复杂度是O(n^2)，空间复杂度是O(1)。思路比较清晰，就不列代码了，有兴趣的朋友可以实现一下哈。
下面我们说说优化的算法。这种方法是基于动态规划的，基本思路就是维护一个长度为n的数组，进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个bar左边最大的高度是多少，存入数组对应元素中，第二次扫描的时候维护右边最大的高度，并且比较将左边和右边小的最大高度（我们成为瓶颈）存入数组对应元素中。这样两遍扫描之后就可以得到每一个bar能承受的最大水量，从而累加得出结果。这个方法只需要两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组，复杂度是O(n)。代码如下：

public int trap(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int max = 0;
    int res = 0;
    int[] container = new int[A.length];
    for(int i=0;i<A.length;i++)
    {
        container[i]=max;
        max = Math.max(max,A[i]);
    }
    max = 0;
    for(int i=A.length-1;i>=0;i--)
    {
        container[i] = Math.min(max,container[i]);
        max = Math.max(max,A[i]);
        res += container[i]-A[i]>0?container[i]-A[i]:0;
    }    
    return res;
}

这个方法算是一种常见的技巧，从两边各扫描一次得到我们需要维护的变量，通常适用于当前元素需要两边元素来决定的问题，非常类似的题目是Candy，有兴趣的朋友可以看看哈。
上面的方法非常容易理解，实现思路也很清晰，不过要进行两次扫描，复杂度前面的常数得是2，接下来我们要介绍另一种方法，相对不是那么好理解，但是只需要一次扫描就能完成。基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。代码如下：

public int trap(int[] A) {
    if(A==null || A.length ==0)
        return 0;
    int l = 0;
    int r = A.length-1;
    int res = 0;
    while(l<r)
    {
        int min = Math.min(A[l],A[r]);
        if(A[l] == min)
        {
            l++;
            while(l<r && A[l]<min)
            {
                res += min-A[l];
                l++;
            }
        }
        else
        {
            r--;
            while(l<r && A[r]<min)
            {
                res += min-A[r];
                r--;
            }
        }
    }
    return res;
}

这个算法每个元素只被访问一次，所以时间复杂度是O(n)，并且常数是1，比前面的方法更优一些，不过理解起来需要想得比较清楚。
这种两边往中间夹逼的方法也挺常用的，它的核心思路就是向中间夹逼时能确定接下来移动一侧窗口不可能使结果变得更好，所以每次能确定移动一侧指针，直到相遇为止。这种方法带有一些贪心，用到的有Two Sum，Container With Most Water，都是不错的题目，有兴趣的朋友可以看看哈。

First Missing Positive -- LeetCode

原题链接: http://oj.leetcode.com/problems/first-missing-positive/
这道题要求用线性时间和常量空间，思想借鉴到了Counting sort中的方法，不了解的朋友可以参见Counting sort - Wikipedia。既然不能用额外空间，那就只有利用数组本身，跟Counting sort一样，利用数组的index来作为数字本身的索引，把正数按照递增顺序依次放到数组中。即让A[0]=1, A[1]=2, A[2]=3, ... , 这样一来，最后如果哪个数组元素违反了A[i]=i+1即说明i+1就是我们要求的第一个缺失的正数。对于那些不在范围内的数字，我们可以直接跳过，比如说负数，0，或者超过数组长度的正数，这些都不会是我们的答案。代码如下：

public int firstMissingPositive(int[] A) {
    if(A==null || A.length==0)
    {
        return 1;
    }
    for(int i=0;i<A.length;i++)
    {
        if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i])
        {
            int temp = A[A[i]-1];
            A[A[i]-1] = A[i];
            A[i] = temp;
            i--;
        }
    }
    for(int i=0;i<A.length;i++)
    {
        if(A[i]!=i+1)
            return i+1;
    }
    return A.length+1;
}

实现中还需要注意一个细节，就是如果当前的数字所对应的下标已经是对应数字了，那么我们也需要跳过，因为那个位置的数字已经满足要求了，否则会出现一直来回交换的死循环。这样一来我们只需要扫描数组两遍，时间复杂度是O(2*n)=O(n)，而且利用数组本身空间，只需要一个额外变量，所以空间复杂度是O(1)。
这道题个人还是比较喜欢的，既有一点算法思想，在实现中又有一些注意细节，而且整体来说模型比较简单，很适合在面试中出现。

Combination Sum II -- LeetCode

原题链接: http://oj.leetcode.com/problems/combination-sum-ii/
这道题跟Combination Sum非常相似，不了解的朋友可以先看看，唯一的区别就是这个题目中单个元素用过就不可以重复使用了。乍一看好像区别比较大，但是其实实现上只需要一点点改动就可以完成了，就是递归的时候传进去的index应该是当前元素的下一个。代码如下：

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num == null || num.length==0)
        return res;
    Arrays.sort(num);
    helper(num,0,target,new ArrayList<Integer>(),res);
    return res;
}
private void helper(int[] num, int start, int target, ArrayList<Integer> item,
ArrayList<ArrayList<Integer>> res)
{
    if(target == 0)
    {
        res.add(new ArrayList<Integer>(item));
        return;
    }
    if(target<0 || start>=num.length)
        return;
    for(int i=start;i<num.length;i++)
    {
        if(i>start && num[i]==num[i-1]) continue;
        item.add(num[i]);
        helper(num,i+1,target-num[i],item,res);
        item.remove(item.size()-1);
    }
}

在这里我们还是需要在每一次for循环前做一次判断，因为虽然一个元素不可以重复使用，但是如果这个元素重复出现是允许的，但是为了避免出现重复的结果集，我们只对于第一次得到这个数进行递归，接下来就跳过这个元素了，因为接下来的情况会在上一层的递归函数被考虑到，这样就可以避免重复元素的出现。这个问题可能会觉得比较绕，大家仔细想想就明白了哈。

Combination Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/combination-sum/
这个题是一个NP问题，方法仍然是N-Queens中介绍的套路。基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的。代码如下：

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(candidates == null || candidates.length==0)
        return res;
    Arrays.sort(candidates);
    helper(candidates,0,target,new ArrayList<Integer>(),res);
    return res;
}
private void helper(int[] candidates, int start, int target, ArrayList<Integer> item, 
ArrayList<ArrayList<Integer>> res)
{
    if(target<0)
        return;
    if(target==0)
    {
        res.add(new ArrayList<Integer>(item));
        return;
    }
    for(int i=start;i<candidates.length;i++)
    {
        if(i>0 && candidates[i]==candidates[i-1])
            continue;
        item.add(candidates[i]);
        helper(candidates,i,target-candidates[i],item,res);
        item.remove(item.size()-1);
    }
}

注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。这道题有一个非常类似的题目Combination Sum II，有兴趣的朋友可以看看，一次搞定两个题哈。

Sudoku Solver -- LeetCode

原题链接: http://oj.leetcode.com/problems/sudoku-solver/
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空。大家可以看出代码结构和N-Queens是完全一样的。判合法可以用Valid Sudoku做为subroutine，但是其实在这里因为每次进入时已经保证之前的board不会冲突，所以不需要判断整个盘，只需要看当前加入的数字和之前是否冲突就可以，这样可以大大提高运行效率，毕竟判合法在程序中被多次调用。实现的代码如下：

public void solveSudoku(char[][] board) {
    if(board == null || board.length != 9 || board[0].length !=9)  
        return;  
    helper(board,0,0);
}
private boolean helper(char[][] board, int i, int j)
{
    if(j>=9)
        return helper(board,i+1,0);
    if(i==9)
    {
        return true;
    }
    if(board[i][j]=='.')
    {
        for(int k=1;k<=9;k++)
        {
            board[i][j] = (char)(k+'0');
            if(isValid(board,i,j))
            {
                if(helper(board,i,j+1))
                    return true;
            }
            board[i][j] = '.';
        }
    }
    else
    {
        return helper(board,i,j+1);
    }
    return false;
}
private boolean isValid(char[][] board, int i, int j)
{
    for(int k=0;k<9;k++)
    {
        if(k!=j && board[i][k]==board[i][j])
            return false;
    }
    for(int k=0;k<9;k++)
    {
        if(k!=i && board[k][j]==board[i][j])
            return false;
    }        
    for(int row = i/3*3; row<i/3*3+3; row++)
    {
        for(int col=j/3*3; col<j/3*3+3; col++)
        {
            if((row!=i || col!=j) && board[row][col]==board[i][j])
                return false;
        }
    }
    return true;
}

再强调一下哈，以上方法是一个非常典型的套路，大部分NP问题的都是可以这个方法，比如N-Queens，Combination Sum，Combinations，Permutations等。