Add Binary -- LeetCode

原题链接: http://oj.leetcode.com/problems/add-binary/
这道题跟Add Two Numbers很类似，代码结构很接近。从低位开始，一直相加并且维护进位。和Add Two Numbers的区别是这个题目低位在后面，所以要从string的尾部往前加。时间复杂度是O(max(m,n))，m和n分别是两个字符串的长度，空间复杂度是结果的长度O(max(m,n))。代码如下：

public String addBinary(String a, String b) {
    if(a==null || a.length()==0)
        return b;
    if(b==null || b.length()==0)
        return a;
    int i=a.length()-1;
    int j=b.length()-1;
    int carry = 0;
    StringBuilder res = new StringBuilder();
    while(i>=0&&j>=0)
    {
        int digit = (int)(a.charAt(i)-'0'+b.charAt(j)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        i--;
        j--;
    }
    while(i>=0)
    {
        int digit = (int)(a.charAt(i)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        i--;
    }
    while(j>=0)
    {
        int digit = (int)(b.charAt(j)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        j--;
    }      
    if(carry>0)
    {
        res.append(carry);
    }
    return res.reverse().toString();
}

最后有一个小细节要注意一下，就是我们维护的res是把低位放在前面，为了满足结果最后要进行一次reverse。

Binary Tree Inorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-inorder-traversal/
通常，实现二叉树的遍历有两个常用的方法：一是用递归，二是使用栈实现的迭代方法。下面分别介绍。
递归应该最常用的算法，相信大家都了解，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。代码如下：

public ArrayList<Integer> inorderTraversal(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);
    res.add(root.val);
    helper(root.right,res);
}

接下来是迭代的做法，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。过程中维护一个node表示当前走到的结点（不是中序遍历的那个结点），实现的代码如下：

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

最后我们介绍一种比较复杂的方法，这个问题我有个朋友在去google onsite的时候被问到了，就是如果用常量空间来中序遍历一颗二叉树。这种方法叫 Morris Traversal。想用O(1)空间进行遍历，因为不能用栈作为辅助空间来保存付节点的信息，重点在于当访问到子节点的时候如何重新回到父节点（当然这里是指没有父节点指针，如果有其实就比较好办，一直找遍历的后驱结点即可）。Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。
算法具体分情况如下：
1. 如果当前结点的左孩子为空，则输出当前结点并将其当前节点赋值为右孩子。
2. 如果当前节点的左孩子不为空，则寻找当前节点在中序遍历下的前驱节点（也就是当前结点左子树的最右孩子）。接下来分两种情况：
 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。然后将当前节点更新为当前节点的左孩子。
 b) 如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将它的右孩子重新设为空（恢复树的结构）。输出当前节点。当前节点更新为当前节点的右孩子。
代码如下：

public ArrayList<Integer> inorderTraversal(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)
            {
                pre.right = cur;
                cur = cur.left;
            }
            else
            {
                pre.right = null;
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

接下来我们来分析一下时间复杂度。咋一看可能会觉得时间复杂度是O(nlogn)，因为每次找前驱是需要logn，总共n个结点。但是如果仔细分析会发现整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，而n个结点的二叉树中有n-1条边，所以时间复杂度是O(2*n)=O(n)，仍然是一个线性算法。空间复杂度的话我们分析过了，只是两个辅助指针，所以是O(1)。

总结一下，上面介绍了三种方法递归，迭代和Morris来实现树的中序遍历，这道题看上去很简单，但是大家还是不能满足于递归的方法，有些面试还是会在简单问题上要求很高的。对于树的 Binary Tree Preorder Traversal 和 Binary Tree Postorder Traversal，也有相应的三种方法，大家可以练习一下。

Pow(x, n) -- LeetCode

原题链接: http://oj.leetcode.com/problems/powx-n/
这道题是一道数值计算的题目，因为指数是可以使结果变大的运算，所以要注意越界的问题。如同我在Sqrt(x)这道题中提到的，一般来说数值计算的题目可以用两种方法来解，一种是以2为基进行位处理的方法，另一种是用二分法。这道题这两种方法都可以解，下面我们分别介绍。
第一种方法在Divide Two Integers使用过，就是把n看成是以2为基的位构成的，因此每一位是对应x的一个幂数，然后迭代直到n到最高位。比如说第一位对应x，第二位对应x*x,第三位对应x^4,...,第k位对应x^(2^(k-1)),可以看出后面一位对应的数等于前面一位对应数的平方，所以可以进行迭代。因为迭代次数等于n的位数，所以算法的时间复杂度是O(logn)。代码如下：

public double pow(double x, int n) {
    if(n==0)
        return 1.0;
    double res = 1.0;   
    if(n<0)
    {
        if(x>=1.0/Double.MAX_VALUE||x<=-1.0/Double.MAX_VALUE)
            x = 1.0/x;
        else
            return Double.MAX_VALUE;
        if(n==Integer.MIN_VALUE)
        {
            res *= x;
            n++;
        }
    }
    n = Math.abs(n);
    boolean isNeg = false;
    if(n%2==1 && x<0)
    {
        isNeg = true;
    }
    x = Math.abs(x);
    while(n>0)
    {
        if((n&1) == 1)
        {
            if(res>Double.MAX_VALUE/x)
                return Double.MAX_VALUE;
            res *= x;
        }
        x *= x;
        n = n>>1;
    }
    return isNeg?-res:res;
}

以上代码中处理了很多边界情况，这也是数值计算题目比较麻烦的地方。比如一开始为了能够求倒数，我们得判断倒数是否越界，后面在求指数的过程中我们也得检查有没有越界。所以一般来说求的时候都先转换为正数，这样可以避免需要双向判断（就是根据符号做两种判断）。
接下来我们介绍二分法的解法，如同我们在Sqrt(x)的方法。不过这道题用递归来解比较容易理解，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，算法复杂度和上面方法一样，也是O(logn)。代码如下：

double pow(double x, int n) {
    if (n == 0) return 1.0;
    double half = pow(x, n/2);
    if (n%2 == 0)
    {
        return half*half;
    }
    else if (n>0)
    {
        return half*half*x;
    }
    else
    {
        return half/x*half;
    }
}

以上代码比较简洁，不过这里有个问题是没有做越界的判断，因为这里没有统一符号，所以越界判断分的情况比较多，不过具体也就是在做乘除法之前判断这些值会不会越界，有兴趣的朋友可以自己填充上哈，这里就不写太啰嗦的代码了。不过实际应用中健壮性还是比较重要的，而且递归毕竟会占用递归栈的空间，所以我可能更推荐第一种解法。

Sqrt(x) -- LeetCode

原题链接: http://oj.leetcode.com/problems/sqrtx/
这是一道数值处理的题目，和Divide Two Integers不同，这道题一般采用数值中经常用的另一种方法：二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，知道左界和右界相遇。算法的时间复杂度是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;
}

二分法在数值计算中非常常见，还是得熟练掌握。其实这个题目还有另一种方法，称为牛顿法。不过他更多的是一种数学方法，算法在这里没有太多体现，不过牛顿法是数值计算中非常重要的方法，所以我还是介绍一下。不太了解牛顿法基本思想的朋友，可以参考一下牛顿法-维基百科。一般牛顿法是用数值方法来解一个f(y)=0的方程（为什么变量在这里用y是因为我们要求的开方是x，避免歧义）。对于这个问题我们构造f(y)=y^2-x，其中x是我们要求平方根的数，那么当f(y)=0时，即y^2-x=0,所以y=sqrt(x),即是我们要求的平方根。f(y)的导数f'(y)=2*y，根据牛顿法的迭代公式我们可以得到y_(n+1)=y_n-f(n)/f'(n)=(y_n+x/y_n)/2。最后根据以上公式来迭代解以上方程。

public int sqrt(int x) {
    if (x == 0) return 0;
    double lastY = 0;
    double y = 1;
    while (y != lastY)
    {
        lastY = y;
        y = (y + x / y) / 2;
    }
    return (int)(y);
}

实际面试遇到的题目可能不是对一个整数开方，而是对一个实数。方法和整数其实是一致的，只是结束条件换成左界和右界的差的绝对值小于某一个epsilon（极小值）即可。这里注意一个小问题，就是在java中我们可以用==来判断两个double是否相等，而在C++中我们则需要通过两个数的绝对值差小于某个极小值来判断两个double的相等性。实际上两个double因为精度问题往往是不可能每一位完全相等的，java中只是帮我们做了这种判定。
比较典型的数值处理的题目还有Divide Two Integers，Pow(x,n)等，其实方法差不多，一般就是用二分法或者以2为基进行位处理的方法。

Divide Two Integers -- LeetCode

原题链接: http://oj.leetcode.com/problems/divide-two-integers/
这道题属于数值处理的题目，对于整数处理的问题，在Reverse Integer中我有提到过，比较重要的注意点在于符号和处理越界的问题。对于这道题目，因为不能用乘除法和取余运算，我们只能使用位运算和加减法。比较直接的方法是用被除数一直减去除数，直到为0。这种方法的迭代次数是结果的大小，即比如结果为n，算法复杂度是O(n)。
那么有没有办法优化呢？ 这个我们就得使用位运算。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k，然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度为O(logn)。代码如下：

public int divide(int dividend, int divisor) {
    if(divisor==0)
        return Integer.MAX_VALUE;
    
    int res = 0;
    if(dividend==Integer.MIN_VALUE)
    {
        res = 1;

        if(divisor == -1)
        {
            return Integer.MAX_VALUE;
        }
        dividend += Math.abs(divisor);
    }
    if(divisor==Integer.MIN_VALUE)
        return res;
    boolean isNeg = ((dividend^divisor)>>>31==1);
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    int digit = 0;
    while(divisor<=(dividend>>1))
    {
        divisor <<= 1;
        digit++;
    }
    while(digit>=0)
    {
        if(dividend>=divisor)
        {
            dividend -= divisor;
            res += 1<<digit;
        }
        divisor >>= 1;
        digit--;
    }
    return isNeg?-res:res;
}

这种数值处理的题目在面试中还是比较常见的，类似的题目有Sqrt(x)，Pow(x, n)等。上述方法在其他整数处理的题目中也可以用到，大家尽量熟悉实现这些问题。

Remove Duplicates from Sorted Array -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
这道题跟Remove Element类似，也是考察数组的基本操作，属于面试中比较简单的题目。做法是维护两个指针，一个保留当前有效元素的长度，一个从前往后扫，然后跳过那些重复的元素。因为数组是有序的，所以重复元素一定相邻，不需要额外记录。时间复杂度是O(n)，空间复杂度O(1)。代码如下：

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

类似的题目有Remove Duplicates from Sorted List，那道题是在数组中操作，还有Remove Duplicates from Sorted Array II，这个题目操作有所不同，不过难度也差不多，有兴趣的朋友可以看看。

Remove Element -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-element/
这道题是比较简单的数组操作，思路是一个指针从前往后走，如果遇到要删除的元素，就从后面调一个替换它，直到结束。复杂度是O(n)，因为每个元素最多被访问一次。比较简练的实现代码如下：

public int removeElement(int[] A, int elem) {
    if(A==null)
        return 0;
    int len = A.length-1;
    for(int i=0;i<=len;i++)
    {
        if(A[i]==elem)
        {
            A[i--] = A[len--];
        }
    }
    return len+1;
}

如果想要减少赋值的次数，可以把在尾部也是删除元素的跳过去，那样代码会稍微啰嗦一点。这道题目有出现也是作为电面的第一道题，属于难度较低的，所以大家尽量做到一遍对，不要有bug比较好。

Reverse Nodes in k-Group -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-nodes-in-k-group/
这道题是Swap Nodes in Pairs的扩展，Swap Nodes in Pairs其实是这道题k=2的特殊情况，大家可以先练习一下。不过实现起来还是比较不一样的，因为要处理比较general的情形。基本思路是这样的，我们统计目前节点数量，如果到达k，就把当前k个结点reverse，这里需要reverse linked list的subroutine。这里我们需要先往前走，到达k的时候才做reverse，所以总体来说每个结点会被访问两次。总时间复杂度是O(2*n)=O(n)，空间复杂度是O(1)。实现的代码如下：

public ListNode reverseKGroup(ListNode head, int k) {
    if(head == null)
    {
        return null;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int count = 0;
    ListNode pre = dummy;
    ListNode cur = head;
    while(cur != null)
    {
        count ++;
        ListNode next = cur.next;
        if(count == k)
        {
            pre = reverse(pre, next);
            count = 0;   
        }
        cur = next;
    }
    return dummy.next;
}
private ListNode reverse(ListNode pre, ListNode end)
{
    if(pre==null || pre.next==null)
        return pre;
    ListNode head = pre.next;
    ListNode cur = pre.next.next;
    while(cur!=end)
    {
        ListNode next = cur.next;
        cur.next = pre.next;
        pre.next = cur;
        cur = next;
    }
    head.next = end;
    return head;
}

有朋友可能会说为什么不边走边reverse，这样可以省一个pass。但是问题是这个题目的要求中最后如果不足k个不需要reverse，所以没法边走边倒。
这道题考查的还是链表的基本操作，其中reverse是一个非常重要的链表操作，大家要多练习，尽量做到一遍做对无bug。

Swap Nodes in Pairs -- LeetCode

原题链接: http://oj.leetcode.com/problems/swap-nodes-in-pairs/
这道题属于链表操作的题目，思路比较清晰，就是每次跳两个节点，后一个接到前面，前一个接到后一个的后面，最后现在的后一个（也就是原来的前一个）接到下下个结点（如果没有则接到下一个）。代码如下：

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

这道题中用了一个辅助指针作为表头，这是链表中比较常用的小技巧，因为这样可以避免处理head的边界情况，一般来说要求的结果表头会有变化的会经常用这个技巧，大家以后会经常遇到。
因为这是一遍过的算法，时间复杂度明显是O(n)，空间复杂度是O(1)。实现中注意细节就可以了，不过我发现现在面试中链表操作的题目出现并不多，所以个人觉得大家练一下就好了，不用花太多时间哈。

Merge k Sorted Lists -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-k-sorted-lists/
这道题目在分布式系统中非常常见，来自不同client的sorted list要在central server上面merge起来。这个题目一般有两种做法，下面一一介绍并且分析复杂度。 第一种做法比较容易想到，就是有点类似于MergeSort的思路,就是分治法，不了解MergeSort的朋友，请参见归并排序-维基百科，是一个比较经典的O(nlogn)的排序算法，还是比较重要的。思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这个题目也是这样，先把k个list分成两半，然后继续划分，知道剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists这道题，不熟悉的朋友可以复习一下。代码如下：

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    if(lists==null || lists.size()==0)
        return null;
    return helper(lists,0,lists.size()-1);
}
private ListNode helper(ArrayList<ListNode> lists, int l, int r)
{
    if(l<r)
    {
        int m = (l+r)/2;
        return merge(helper(lists,l,m),helper(lists,m+1,r));
    }
    return lists.get(l);
}
private ListNode merge(ListNode l1, ListNode l2)
{ 
    ListNode dummy = new ListNode(0);
    dummy.next = l1;
    ListNode cur = dummy;
    while(l1!=null && l2!=null)
    {
        if(l1.val<l2.val)
        {
            l1 = l1.next;
        }
        else
        {
            ListNode next = l2.next;
            cur.next = l2;
            l2.next = l1;
            l2 = next;
        }
        cur = cur.next;
    }
    if(l2!=null)
        cur.next = l2;
    return dummy.next;
}

我们来分析一下上述算法的时间复杂度。假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。如果不了解主定理的朋友，可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。
接下来我们来看第二种方法。这种方法用到了堆的数据结构，思路比较难想到，但是其实原理比较简单。维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。因为每个链表是有序的，每次又是去当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。这个算法每个元素要读取一次，即是k*n次，然后每次读取元素要把新元素插入堆中要logk的复杂度，所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。代码如下：

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){
            @Override
            public int compare(ListNode n1, ListNode n2)
            {
                return n1.val-n2.val;
            }
        });
    for(int i=0;i<lists.size();i++)
    {
        ListNode node = lists.get(i); 
        if(node!=null)
        {
            heap.offer(node);
        }
    }
    ListNode head = null;
    ListNode pre = head;
    while(heap.size()>0)
    {
        ListNode cur = heap.poll();
        if(head == null)
        {
            head = cur;
            pre = head;
        }
        else
        {
            pre.next = cur;
        }
        pre = cur;
        if(cur.next!=null)
            heap.offer(cur.next);
    }
    return head;
}

可以看出两种方法有着同样的时间复杂度，都是可以接受的解法，但是却代表了两种不同的思路，数据结构也不用。个人觉得两种方法都掌握会比较好哈，因为在实际中比较有应用，所以也是比较常考的题目。

Generate Parentheses -- LeetCode

原题链接: http://oj.leetcode.com/problems/generate-parentheses/
这道题其实是关于卡特兰数的，如果只是要输出结果有多少组，那么直接用卡特兰数的公式就可以。关于卡特兰数，请参见卡特兰数-维基百科，里面有些常见的例子，这个概念还是比较重要的，因为很多问题的原型其实都是卡特兰数，大家可以看看。特别是其中

这个递推式的定义，很多这类问题都可以归结成这个表达式。这个题对于C的定义就是第一对括号中包含有几组括号。因为第一组括号中包含的括号对数量都不同，所以不会重复，接下来就是一个递归定义，里面又可以继续用更小的C去求组合可能性。
说完卡特兰数的内容，我们来看看这个具体问题怎么解决。一般来说是用递归的方法，因为可以归结为子问题去操作。在每次递归函数中记录左括号和右括号的剩余数量，然后有两种选择，一个是放一个左括号，另一种是放一个右括号。当然有一些否定条件，比如剩余的右括号不能比左括号少，或者左括号右括号数量都要大于0。正常结束条件是左右括号数量都为0。算法的复杂度是O(结果的数量)，因为卡特兰数并不是一个多项式量级的数字，所以算法也不是多项式复杂度的。代码如下：

public ArrayList<String> generateParenthesis(int n) {
    ArrayList<String> res = new ArrayList<String>();
    if(n<=0)
        return res;
    helper(n,n,new String(),res);
    return res;
}
private void helper(int l, int r, String item, ArrayList<String> res)
{
    if(r<l)
        return;
    if(l==0 && r==0)
    {
        res.add(item);
    }
    if(l>0)
        helper(l-1,r,item+"(",res);
    if(r>0)
        helper(l,r-1,item+")",res);
}

这道题目主要考查的是递归思想的实现，当然如果可以看透背后是一个卡特兰数的模型，会更好一些。

Valid Parentheses -- LeetCode

原题链接: http://oj.leetcode.com/problems/valid-parentheses/
这道题思路比较简单，主要考察对栈数据结构的操作。遇到左括号就入栈，遇到右括号看栈顶左括号是否与当前右括号匹配，匹配继续，否则返回false。算法的时间复杂度是O(n)，空间复杂度也是O(n)。代码如下：

public boolean isValid(String s) {
    if(s==null || s.length()==0)
        return true;
    LinkedList<Character> stack = new LinkedList<Character>();
    for(int i=0;i<s.length();i++)
    {
        switch(s.charAt(i))
        {
            case '(':
            case '{':
            case '[':
                stack.push(s.charAt(i));
                break;
            case ')':
                if(stack.isEmpty() || stack.pop()!='(')
                    return false;
                break;
            case '}':
                if(stack.isEmpty() || stack.pop()!='{')
                    return false;
                break;
            case ']':
                if(stack.isEmpty() || stack.pop()!='[')
                    return false;
                break; 
            default:
                break;
        }
    }
    if(stack.isEmpty())
        return true;
    return false;
}

实现中的小陷阱是注意结束的时候要判一下栈是否为空，不为空仍是不合法的。

Remove Nth Node From End of List -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/
这道题是链表基本操作，主要问题就是如何得到链表的倒数第n个结点，应该是一个比较重要的routine，因为很多题目都要用这个subroutine。思路就是先用一个runner指针走n步，然后再来一个walker从头开始和runner同时向后走，当runner走到链表末尾的时候，walker指针即为倒数第n个结点。算法的时间复杂度是O(链表的长度)，空间复杂度是O(1)。代码如下：

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

原题中假设n总是合法的，但是面试的时候最好不要做这种假设，或者至少要和面试官讨论一下。以上代码是如果n不合法，就直接返回链表头，也就是什么都不做。对于这种corner case，大家还是尽量考虑，因为题目比较简单，更多的只能去关注这些问题。

Letter Combinations of a Phone Number -- LeetCode

原题链接: http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/
这道题目和求组合的思路差不多，比较简单。依次读取数字，然后把数字可以代表的字符依次加到当前的所有结果中，然后进入下一次迭代。假设总共有n个digit，每个digit可以代表k个字符，那么时间复杂度是O(k^n)，就是结果的数量，空间复杂度也是一样。代码如下：

public ArrayList<String> letterCombinations(String digits) {
    ArrayList<String> res = new ArrayList<String>();
        res.add("");
    if(digits==null || digits.length()==0)
        return res;
    for(int i=0;i<digits.length();i++)
    {
        String letters = getLetters(digits.charAt(i));
        ArrayList<String> newRes = new ArrayList<String>();
        for(int j=0;j<res.size();j++)
        {
            for(int k=0;k<letters.length();k++)
            {    
                newRes.add(res.get(j)+Character.toString(letters.charAt(k)));
            }
        }
        res = newRes;
    }
    return res;
}
private String getLetters(char digit)
{
    switch(digit)
    {
        case '2':
            return "abc";
        case '3':
            return "def";
        case '4':
            return "ghi";
        case '5':
            return "jkl";
        case '6':
            return "mno";
        case '7':
            return "pqrs";
        case '8':
            return "tuv";
        case '9':
            return "wxyz";
        case '0':
            return " ";
        default:
            return "";
    }
}

这道题个人觉得没有太多算法和数据结构的思想，但是自己在facebook的面试中遇到了，所以还是要重视一下，就是一些数组操作的小细节。相关的扩展是这道题如何用递归来解，思路其实类似，就是对于当前字符，递归剩下的数字串，然后得到结果后加上自己返回回去，大家可以试试。如果有问题，欢迎留言讨论哈。

3Sum Closest -- LeetCode

原题链接: http://oj.leetcode.com/problems/3sum-closest/
这道题跟3Sum很类似，区别就是要维护一个最小的diff，求出和目标最近的三个和。brute force时间复杂度为O(n^3)，优化的解法是使用排序之后夹逼的方法，总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n),代码如下：

public int threeSumClosest(int[] num, int target) {
    if(num == null || num.length<=2)
        return Integer.MIN_VALUE;
    Arrays.sort(num);
    int closest = num[0]+num[1]+num[2]-target;    
    for(int i=0;i<num.length-2;i++)
    {
        int cur = twoSum(num,target-num[i],i+1);
        if(Math.abs(cur)<Math.abs(closest))
            closest = cur; 
    }
    return target+closest;
}
private int twoSum(int[] num, int target, int start)
{
    int closest = num[start]+num[start+1]-target;
    int l = start;
    int r = num.length-1;
    while(l<r)
    {
        if(num[l]+num[r]==target)
            return 0;
        int diff = num[l]+num[r]-target;
        if(Math.abs(diff)<Math.abs(closest))
            closest = diff;    
        if(num[l]+num[r]>target)
        {
            r--;
        }
        else
        {
            l++;
        }
    }
    return closest;
}

这道题具体的考察点可以参见3Sum，稍微变体一下，其实区别不大。此题更加复杂的扩展是4Sum，请参见4Sum -- LeetCode.

Merge Two Sorted Lists -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-two-sorted-lists/
这道题目比较简单，经典的链表基本操作。维护两个指针对应两个链表，因为一般会以一条链表为基准，比如说l1, 那么如果l1当期那的元素比较小，那么直接移动l1即可，否则将l2当前的元素插入到l1当前元素的前面。算法时间复杂度是O(m+n),m和n分别是两条链表的长度，空间复杂度是O(1)，代码如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode helper = new ListNode(0);
    ListNode pre = helper;
    helper.next = l1;
    while(l1!=null && l2 != null)
    {
        if(l1.val>l2.val)
        {
            ListNode next = l2.next;
            l2.next = pre.next;
            pre.next = l2;
            l2 = next;
        }
        else
        {
            l1 = l1.next;
        }
        pre = pre.next;

    }
    if(l2!=null)
    {
        pre.next = l2;
    }
    return helper.next;
}

这个题类似的有Merge Sorted Array，只是后者是对数组进行合并操作，面试中可能会一起问到。扩展题目Merge k Sorted Lists, 这是一个在分布式系统中比较有用的基本操作，还是需要重视，面试中可以发散出很多问题。

Merge Sorted Array -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-sorted-array/
这是一道数组操作的题目，思路比较明确，就是维护三个index，分别对应数组A，数组B，和结果数组。然后A和B同时从后往前扫，每次迭代中A和B指向的元素大的便加入结果数组中，然后index-1，另一个不动。代码如下：

public void merge(int A[], int m, int B[], int n) {
    if(A==null || B==null)
        return;
    int idx1 = m-1;
    int idx2 = n-1;
    int len = m+n-1;
    while(idx1>=0 && idx2>=0)
    {
        if(A[idx1]>B[idx2])
        {
            A[len--] = A[idx1--];
        }
        else
        {
            A[len--] = B[idx2--];
        }
    }
    while(idx2>=0)
    {
        A[len--] = B[idx2--];
    }        
}

这里从后往前扫是因为这个题目中结果仍然放在A中，如果从前扫会有覆盖掉未检查的元素的可能性。算法的时间复杂度是O(m+n),m和n分别是两个数组的长度，空间复杂度是O(1)。这个题类似的有Merge Two Sorted Lists，只是后者是对于LinkedList操作，面试中可能会一起问到。

Longest Common Prefix -- LeetCode

原题链接: http://oj.leetcode.com/problems/longest-common-prefix/
这道题属于字符串处理的题目，思路比较简单，就是brute force的想法，以第一个字符串为标准，对于每个字符串从第一个字符开始，看看是不是和标准一致，如果不同，则跳出循环返回当前结果，否则继续下一个字符。时间复杂度应该是O(m*n)，m表示字符串的最大长度，n表示字符串的个数，空间复杂度应该是O(m),即字符串的长度，代码如下：

public String longestCommonPrefix(String[] strs) {
    StringBuilder res = new StringBuilder();
    if(strs == null || strs.length==0)
        return res.toString();
    boolean sameFlag = true;
    int idx = 0;
    while(sameFlag)
    {
        for(int i=0;i<strs.length;i++)
        {
            if(strs[i].length()<=idx || strs[i].charAt(idx)!=strs[0].charAt(idx))
            {
                sameFlag = false;
                break;
            }
        }
        if(sameFlag)
            res.append(strs[0].charAt(idx));
        idx++;
    }
    return res.toString();
}

以上代码设置了一个标记，来标记是否结束。细心的读者可能发现中间那个循环index是从0开始，按理说不用对第一个字符串进行判断了，因为他是标准，这么做的目的其实是因为leetcode有一个测试集是空串，如果不对0进行判断，那么就没有设置flag为false，跑到第二层就会越界。当然也可以手动判断一下，这个其实是小问题。
如果有朋友有更优的解法，如果大家这个题有更好的解法，可以留言或者发邮件到linhuanmars@gmail.com给我交流谈论哈。

Roman to Integer -- LeetCode

原题链接: http://oj.leetcode.com/problems/roman-to-integer/
这道题和Integer to Roman一样，也是整数和罗马数字的转换。思路也比较简单，就是维护一个整数，然后如果1下一个字符是对应位的5或者10则减对应位的1，否则加之。遇到5或者10就直接加上对应位的5或者10。时间复杂度是O(字符串的长度)，空间复杂度是O(1)。代码如下：

public int romanToInt(String s) {

    if(s==null || s.length()==0)
        return 0;
    int res = 0;
    for(int i=0;i<s.length();i++)
    {
        switch(s.charAt(i))
        {
            case 'I':
                if(i<s.length()-1 && (s.charAt(i+1)=='V'||s.charAt(i+1)=='X'))
                {
                    res -= 1;
                }
                else
                {
                    res += 1;
                }
                break;
            case 'V':
                res += 5;
                break;
            case 'X':
                if(i<s.length()-1 && (s.charAt(i+1)=='L'||s.charAt(i+1)=='C'))
                {
                    res -= 10;
                }
                else
                {
                    res += 10;
                }
                break;
            case 'L':
                res += 50;
                break;
            case 'C':
                if(i<s.length()-1 && (s.charAt(i+1)=='D'||s.charAt(i+1)=='M'))
                {
                    res -= 100;
                }
                else
                {
                    res += 100;
                }
                break;
            case 'D':
                res += 500;
                break;
            case 'M':
                res += 1000;
                break;
            default:
                return 0;
        }
    }
    return res;
}

题目思路比较清晰，就是简单的字符串操作。

Integer to Roman -- LeetCode

原题链接: http://oj.leetcode.com/problems/integer-to-roman/
这道题比较简单，只要搞清楚每个数字在每个位置应该如何表示就可以，罗马数字对于每个位有三个单位：1,5,10，对于1到9，表示方法如下：
1-3：用1表示；
4:1：5左边加一个1；
5： 直接用5表示；
6-8: 5右边加相应的1；
9： 10左边加一个1。
以下的代码用一个函数来对某一个位用相应的1,5,10进行转换，然后求出每一位依次转换得到结果，因为知道不会超过4000，所以直接求4位出来，算法时间复杂度是O(整数的位数），空间复杂度是O(1)。 代码如下：

public String intToRoman(int num) {
    //I 1
    //V 5
    //X 10
    //L 50
    //C 100
    //D 500
    //M 1,000
    if(num<1 || num>3999)
        return "";
    int digit = 1000;
    ArrayList<Integer> digits = new ArrayList<Integer>();
    while(digit>0)
    {
        digits.add(num/digit);
        num %= digit;
        digit /= 10;
    }
    StringBuilder res = new StringBuilder();
    res.append(convert(digits.get(0),'M',' ', ' '));
    res.append(convert(digits.get(1),'C','D', 'M'));
    res.append(convert(digits.get(2),'X','L', 'C'));
    res.append(convert(digits.get(3),'I','V', 'X'));
    return res.toString();
}
public String convert(int digit, char one, char five, char ten)
{
    StringBuilder res = new StringBuilder();
    switch(digit)
    {
        case 9:
            res.append(one);
            res.append(ten);
            break;
        case 8:
        case 7:
        case 6:
        case 5:
            res.append(five);
            for(int i=5;i<digit;i++)
                res.append(one);
            break;
        case 4:
            res.append(one);
            res.append(five);
            break;   
        case 3:
        case 2:
        case 1:
            for(int i=0;i<digit;i++)
                res.append(one);
            break;   
        default:
            break;
    }
    return res.toString();
}

题目思路很简单，主要就是考察一下对于整数和字符串的操作，属于比较基本的题目。

Container With Most Water -- LeetCode

原题链接: http://oj.leetcode.com/problems/container-with-most-water/
首先一般我们都会想到brute force的方法，思路很简单，就是对每一对pair都计算一次容积，然后去最大的那个，总共有n*(n-1)/2对pair，所以时间复杂度是O(n^2)。
接下来我们考虑如何优化。思路有点类似于Two Sum中的第二种方法--夹逼。从数组两端走起，每次迭代时判断左pointer和右pointer指向的数字哪个大，如果左pointer小，意味着向左移动右pointer不可能使结果变得更好，因为瓶颈在左pointer，移动右pointer只会变小，所以这时候我们选择左pointer右移。反之，则选择右pointer左移。在这个过程中一直维护最大的那个容积。代码如下：

public int maxArea(int[] height) {
    if(height==null || height.length==0)
        return 0;
    int l = 0;
    int r = height.length-1;
    int maxArea = 0;
    while(l<r)
    {
        maxArea = Math.max(maxArea, Math.min(height[l],height[r])*(r-l));
        if(height[l]<height[r])
            l++;
        else
            r--;
    }
    return maxArea;
}

以上的算法，因为左pointer只向右移，右pointer只向左移，直到相遇为止，所以两者相加只走过整个数组一次，时间复杂度为O(n),空间复杂度是O(1)。该算法利用了移动指针可确定的规律，做了一步贪心，实现了时间复杂度的降低。

Regular Expression Matching -- LeetCode

原题链接: http://oj.leetcode.com/problems/regular-expression-matching/
这个题目比较常见，但是难度还是比较大的。我们先来看看brute force怎么解决。基本思路就是先看字符串s和p的从i和j开始的子串是否匹配，用递归的方法直到串的最后，最后回溯回来得到结果。假设现在走到s的i位置，p的j位置，情况分为下列两种：
(1)p[j+1]不是'*'。情况比较简单，只要判断当前s的i和p的j上的字符是否一样（如果有p在j上的字符是'.',也是相同），如果不同，返回false，否则，递归下一层i+1，j+1;
(2)p[j+1]是'*'。那么此时看从s[i]开始的子串，假设s[i],s[i+1],...s[i+k]都等于p[j]那么意味着这些都有可能是合适的匹配，那么递归对于剩下的(i,j+2),(i+1,j+2),...,(i+k,j+2)都要尝试（j+2是因为跳过当前和下一个'*'字符）。
实现代码如下：

public boolean isMatch(String s, String p) {
    return helper(s,p,0,0);
}
private boolean helper(String s, String p, int i, int j)
{
    if(j==p.length())
        return i==s.length();
    
    if(j==p.length()-1 || p.charAt(j+1)!='*')
    {
        if(i==s.length()|| s.charAt(i)!=p.charAt(j) && p.charAt(j)!='.')
            return false;
        else
            return helper(s,p,i+1,j+1);
    }
    //p.charAt(j+1)=='*'
    while(i<s.length() && (p.charAt(j)=='.' || s.charAt(i)==p.charAt(j)))
    {
        if(helper(s,p,i,j+2))
            return true;
        i++;
    }
    return helper(s,p,i,j+2);
}

接下来我们考虑如何优化brute force算法，熟悉动态规划的朋友可能发现了，其实这个思路已经很接近动态规划了。动态规划基本思想就是把我们计算过的历史信息记录下来，等到要用到的时候就直接使用，不用重新计算。在这个题里面，假设我们维护一个布尔数组res[i][j],代表s的前i个字符和p的前j个字符是否匹配(注意这里res的维度是s.length()+1,p.length()+1)。递推公式跟上面类似，分三种种情况：
(1)p[j+1]不是'*'。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是'.',也是相同），并且res[i][j]==true，则res[i+1][j+1]也为true，res[i+1][j+1]=false;
(2)p[j+1]是'*'，但是p[j]!='.'。那么只要以下条件有一个满足即可对res[i+1][j+1]赋值为true：
    1)res[i+1][j]为真（'*'只取前面字符一次）;
    2)res[i+1][j-1]为真（'*'前面字符一次都不取，也就是忽略这两个字符）;
    3)res[i][j+1] && s[i]==s[i-1] && s[i-1]==p[j-1](这种情况是相当于i从0到s.length()扫过来，如果p[j+1]对应的字符是‘*’那就意味着接下来的串就可以依次匹配下来，如果下面的字符一直重复，并且就是‘*’前面的那个字符）。
(3)p[j+1]是'*'，并且p[j]=='.'。因为".*"可以匹配任意字符串，所以在前面的res[i+1][j-1]或者res[i+1][j]中只要有i+1是true，那么剩下的res[i+1][j+1],res[i+2][j+1],...,res[s.length()][j+1]就都是true了。
这道题有个很重要的点，就是实现的时候外层循环应该是p,然后待匹配串s内层循环扫过来。代码如下：

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

对比以上两种做法，其实思路基本类似，动态规划优势在于对于前面计算过得信息不需要再重复计算，而brute force则每次重新计算。上面两种算法中，动态规划的时间复杂度是O(m*n),空间复杂度也是O(m*n)，假设s的长度为n, p的长度为m。而brute force的递归算法最坏情况是指数量级的复杂度。
这种题目在面试中算是比较难的题目，因为分情况比较多，如果不熟悉比较难在面试中理清思路并且做对，我不是很喜欢，但是在面经中却经常看到，所以还是得搞熟悉比较好。类似的题目有Wildcard Matching，那个还更简单一些，不过思路是基本一致的，只是少分一点情况。

Minimum Depth of Binary Tree -- LeetCode

原题链接：http://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
这道题是树的题目，其实跟Maximum Depth of Binary Tree非常类似，只是这道题因为是判断最小深度，所以必须增加一个叶子的判断（因为如果一个节点如果只有左子树或者右子树，我们不能取它左右子树中小的作为深度，因为那样会是0，我们只有在叶子节点才能判断深度，而在求最大深度的时候，因为一定会取大的那个，所以不会有这个问题）。这道题同样是递归和非递归的解法，递归解法比较常规的思路，比Maximum Depth of Binary Tree多加一个左右子树的判断，代码如下：

public int minDepth(TreeNode root) {
    if(root == null)
        return 0;
    if(root.left == null)
        return minDepth(root.right)+1;
    if(root.right == null)
        return minDepth(root.left)+1;
    return Math.min(minDepth(root.left),minDepth(root.right))+1;
}

非递归解法同样采用层序遍历(相当于图的BFS），只是在检测到第一个叶子的时候就可以返回了，代码如下：

public int minDepth(TreeNode root) {
    if(root == null)
        return 0;
    LinkedList queue = new LinkedList();
    int curNum = 0;
    int lastNum = 1;
    int level = 1;
    queue.offer(root);
    while(!queue.isEmpty())
    {
        TreeNode cur = queue.poll();
        if(cur.left==null && cur.right==null)
            return level;
        lastNum--;
        if(cur.left!=null)
        {
            queue.offer(cur.left);
            curNum++;
        }
        if(cur.right!=null)
        {
            queue.offer(cur.right);
            curNum++;
        }
        if(lastNum==0)
        {
            lastNum = curNum;
            curNum = 0;
            level++;
        }
    }
    return 0;
}

Palindrome Number -- LeetCode

原题链接: http://oj.leetcode.com/problems/palindrome-number/
这道题跟Reverse Integer差不多，也是考查对整数的操作，相对来说可能还更加简单，因为数字不会变化，所以没有越界的问题。基本思路是每次去第一位和最后一位，如果不相同则返回false，否则继续直到位数为0。代码如下：

public boolean isPalindrome(int x) {
    if(x<0)
        return false;
    int div = 1;
    while(div<=x/10)
        div *= 10;
    while(x>0)
    {
        if(x/div!=x%10)
            return false;
        x = (x%div)/10;
        div /= 100;
    }
    return true;
}

这个题和Longest Palindromic Substring也很接近，只是处理的数据结构有所不同。如果大家这个题有更好的解法，欢迎讨论哈。可以留言或者发邮件到linhuanmars@gmail.com给我，多谢~

String to Integer (atoi) -- LeetCode

原题链接：http://oj.leetcode.com/problems/string-to-integer-atoi/
这道题还是对于Integer的处理，在Reverse Integer这道题中我有提到，这种题的考察重点并不在于问题本身，而是要注意corner case的处理，整数一般有两点，一个是正负符号问题，另一个是整数越界问题。思路比较简单，就是先去掉多余的空格字符，然后读符号（注意正负号都有可能，也有可能没有符号），接下来按顺序读数字，结束条件有三种情况：（1）异常字符出现（按照C语言的标准是把异常字符起的后面全部截去，保留前面的部分作为结果）；（2）数字越界（返回最接近的整数）；（3）字符串结束。代码如下：

public int atoi(String str) {
    if(str==null)
    {
        return 0;
    }
    str = str.trim();
    if(str.length()==0)
        return 0;
    boolean isNeg = false;
    int i = 0;
    if(str.charAt(0)=='-' || str.charAt(0)=='+')
    {
        i++;
        if(str.charAt(0)=='-')
            isNeg = true;
    }
    int res = 0;
    while(i<str.length())
    {
        if(str.charAt(i)<'0'||str.charAt(i)>'9')
            break;
        int digit = (int)(str.charAt(i)-'0');
        if(isNeg && res>-((Integer.MIN_VALUE+digit)/10))
            return Integer.MIN_VALUE;
        else if(!isNeg && res>(Integer.MAX_VALUE-digit)/10)
            return Integer.MAX_VALUE;
        res = res*10+digit;
        i++;
    }
    return isNeg?-res:res;
}

这道题主要考察整数处理，注意点上面已经提到过，因为这个问题是C语言的一个基本问题，面试中还是有可能出现，相对比较底层，边缘情况的处理是关键，可能面试tester的职位会更常见一些。

Reverse Integer -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-integer/
这道题思路非常简单，就是按照数字位反转过来就可以，基本数字操作。但是这种题的考察重点并不在于问题本身，越是简单的题目越要注意细节，一般来说整数的处理问题要注意的有两点，一点是符号，另一点是整数越界问题。代码如下：

public int reverse(int x) {
    if(x==Integer.MIN_VALUE)
        return 0;
    int num = Math.abs(x);
    int res = 0;
    while(num!=0)
    {
        if(res>(Integer.MAX_VALUE-num%10)/10)
            return 0;
        res = res*10+num%10;
        num /= 10;
    }
    return x>0?res:-res;
}

上面的代码为了后面方便处理，先将数字转为正数。注意Integer.MIN_VALUE的绝对值是比Integer.MAX_VALUE大1的，所以经常要单独处理。如果不先转为正数也可以，只是在后面要对符号进行一下判断。这种题目考察的就是数字的基本处理，面试的时候尽量不能错，而且对于corner case要尽量进行考虑，一般来说都是面试的第一道门槛。

ZigZag Conversion -- LeetCode

原题链接: http://oj.leetcode.com/problems/zigzag-conversion/
这道题是cc150里面的题目了，其实比较简单，只要看出来他其实每个zigzag是2*m-2个字符就可以，这里m是结果的行的数量。接下来就是对于每一行先把往下走的那一列的字符加进去，然后有往上走的字符再加进去即可。时间复杂度是O(n),空间复杂度是O(1),代码如下：

public String convert(String s, int nRows) {
    if(s == null || s.length()==0 || nRows <=0)
        return "";
    if(nRows == 1)
        return s;
    StringBuilder res = new StringBuilder();
    int size = 2*nRows-2;
    for(int i=0;i<nRows;i++)
    {
        for(int j=i;j<s.length();j+=size)
        {
            res.append(s.charAt(j));
            if(i!=0 && i!=nRows-1 && j+size-2*i<s.length())
                res.append(s.charAt(j+size-2*i));
        }                
    }
    return res.toString();
}

实现上要注意最后如果字符长度到了，就不需要添加了。 这道题也没有什么扩展，我觉得面试中考到的几率不大，基本就是字符串的操作。

Longest Palindromic Substring -- LeetCode

原题链接: http://oj.leetcode.com/problems/longest-palindromic-substring/
这道题是比较常考的题目，求回文子串，一般有两种方法。 第一种方法比较直接，实现起来比较容易理解。基本思路是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）往两边同时进行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)，代码如下：

public String longestPalindrome(String s) {
    if(s == null || s.length()==0)
        return "";
    int maxLen = 0;
    String res = "";
    for(int i=0;i<2*s.length()-1;i++)
    {
        int left = i/2;
        int right = i/2;
        if(i%2==1)
            right++;
        String str = lengthOfPalindrome(s,left,right);
        if(maxLen<str.length())
        {
            maxLen = str.length();
            res = str;
        }
    }
    return res;
}
private String lengthOfPalindrome(String s, int left, int right)
{
    
    while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right))
    {
        left--;
        right++;
    }
    return s.substring(left+1,right);
}

而第二种方法是用动态规划，思路比较复杂一些，但是实现代码会比较简短。基本思路是外层循环i从后往前扫，内层循环j从i当前字符扫到结尾处。过程中使用的历史信息是从i+1到n之间的任意子串是否是回文已经被记录下来，所以不用重新判断，只需要比较一下头尾字符即可。这种方法使用两层循环，时间复杂度是O(n^2)。而空间上因为需要记录任意子串是否为回文，需要O(n^2)的空间，代码如下：

public String longestPalindrome(String s) {
    if(s == null || s.length()==0)
        return "";
    boolean[][] palin = new boolean[s.length()][s.length()];
    String res = "";
    int maxLen = 0;
    for(int i=s.length()-1;i>=0;i--)
    {
        for(int j=i;j<s.length();j++)
        {
            if(s.charAt(i)==s.charAt(j) && (j-i<=2 || palin[i+1][j-1]))
            {
                palin[i][j] = true;
                if(maxLen<j-i+1)
                {
                    maxLen=j-i+1;
                    res = s.substring(i,j+1);
                }
            }
        }
    }
    return res;
}

综上所述，两种方法的时间复杂度都是O(n^2)。而空间上来看第一种方法是常量的，比第二种方法优。这个题目中假设最长回文子串只有一个，实际面试中一般不做这种假设，如果要返回所有最长回文串，只需要稍做变化就可以，维护一个集合，如果等于当前最大的，即加入集合，否则，如果更长，则清空集合，加入当前这个。实际面试会有各种变体，感觉平常还是要多想才行。

Add Two Numbers -- LeetCode

原题链接: http://oj.leetcode.com/problems/add-two-numbers/
这道题比较简单，是cc150里面的题，思路很明确，就是按照位数读下去，维护当前位和进位，时间复杂度是O(n),空间复杂度是O(1).代码如下：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    int digit = 0;
    ListNode head = null;
    ListNode pre = null;
    while(l1!=null && l2!=null)
    {
        digit = (l1.val+l2.val+carry)%10;
        carry = (l1.val+l2.val+carry)/10;
        ListNode newNode = new ListNode(digit);
        if(head==null)
            head = newNode;
        else
            pre.next = newNode;
        pre = newNode;
        l1 = l1.next;
        l2 = l2.next;
    }
    while(l1!=null)
    {
        digit = (l1.val+carry)%10;
        carry = (l1.val+carry)/10;
        ListNode newNode = new ListNode(digit);
        if(head==null)
            head = newNode;
        else
            pre.next = newNode;
        pre = newNode;
        l1 = l1.next;            
    }
    while(l2!=null)
    {
        digit = (l2.val+carry)%10;
        carry = (l2.val+carry)/10;
        ListNode newNode = new ListNode(digit);
        if(head==null)
            head = newNode;
        else
            pre.next = newNode;
        pre = newNode;
        l2 = l2.next;            
    }        
    if(carry>0)
    {
        ListNode newNode = new ListNode(carry);
        pre.next = newNode;
    }
    return head;
}

实现中注意维护进位，陷阱的话记住最后还要判一下有没有进位，如果有再生成一位。
这道题还是有一些扩展的，比如这个其实是BigInteger的相加，数据结果不一定要用链表，也可以是数组，面试中可能两种都会问而且实现。然后接下来可以考一些OO设计的东西，比如说如果这是一个类应该怎么实现，也就是把数组或者链表作为成为成员变量，再把这些操作作为成员函数，进一步的问题可能是如何设计constructor，这个问题除了基本的还得对内置类型比如int, long的constructor, 类似于BigInteger(int num), BigInteger(int long). 总体来说问题还是比较简单，但是这种问题不能出错，所以还是要谨慎对待。

Longest Substring Without Repeating Characters -- LeetCode

原题链接: http://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
这道题用的方法是在LeetCode中很常用的方法，对于字符串的题目非常有用。 首先brute force的时间复杂度是O(n^3), 对每个substring都看看是不是有重复的字符，找出其中最长的，复杂度非常高。优化一些的思路是稍微动态规划一下，每次定一个起点，然后从起点走到有重复字符位置，过程用一个HashSet维护当前字符集，认为是constant操作，这样算法要进行两层循环，复杂度是O(n^2)。
最后，我们介绍一种线性的算法，也是这类题目最常见的方法。基本思路是维护一个窗口，每次关注窗口中的字符串，在每次判断中，左窗口和右窗口选择其一向前移动。同样是维护一个HashSet, 正常情况下移动右窗口，如果没有出现重复则继续移动右窗口，如果发现重复字符，则说明当前窗口中的串已经不满足要求，继续移动有窗口不可能得到更好的结果，此时移动左窗口，直到不再有重复字符为止，中间跳过的这些串中不会有更好的结果，因为他们不是重复就是更短。因为左窗口和右窗口都只向前，所以两个窗口都对每个元素访问不超过一遍，因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n). 代码如下：

public int lengthOfLongestSubstring(String s) {
    if(s==null || s.length()==0)
        return 0;
    HashSet<Character> set = new HashSet<Character>();
    int max = 0;
    int walker = 0;
    int runner = 0;
    while(runner<s.length())
    {
        if(set.contains(s.charAt(runner)))
        {
            if(max<runner-walker)
            {
                max = runner-walker;
            }
            while(s.charAt(walker)!=s.charAt(runner))
            {
                set.remove(s.charAt(walker));
                walker++;
            }
            walker++;
        }
        else
        {
            set.add(s.charAt(runner));
        }
        runner++;
    }
    max = Math.max(max,runner-walker);
    return max;
}

这道题思想在字符串处理的题中还是比较重要的，实现上主要是HashSet和数组index的操作。扩展的题目有Substring with Concatenation of All Words，Minimum Window Substring，思路是非常接近的，只是操作上会更加繁琐一些。

Median of Two Sorted Arrays -- LeetCode

原题链接: http://oj.leetcode.com/problems/median-of-two-sorted-arrays/
这道题比较直接的想法就是用Merge Sorted Array这个题的方法把两个有序数组合并，当合并到第(m+n)/2个元素的时候返回那个数即可，而且不用把结果数组存起来。算法时间复杂度是O(m+n)，空间复杂度是O(1)。因为代码比较简单，就不写出来了，跟Merge Sorted Array比较类似，大家可以参照这个题目的解法。
接下来我们考虑有没有优化的算法。优化的思想来源于order statistics，在算法导论10.3节中提到。问题等价于求两个array的第k=(m+n)/2（假设m和n分别是两个数组的元素个数）大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(假设是A[k/2],B[k/2])，如果两个A[k/2]=B[k/2]，说明当前这个数即为两个数组剩余元素的第k大的数，如果A[k/2]>B[k/2], 那么说明B的前k/2个元素都不是我们要的第k大的数，反之则排除A的前k/2个，如此每次可以排除k/2个元素，最终k=1时即为结果。总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。比起第一种解法有明显的提高，代码如下：

public double findMedianSortedArrays(int A[], int B[]) {
    if((A.length+B.length)%2==1)
        return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1);
    else
        return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2)  
               +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0;
}
private int helper(int A[], int B[], int i, int i2, int j, int j2, int k)
{
    int m = i2-i+1;
    int n = j2-j+1;
    if(m>n)
        return helper(B,A,j,j2,i,i2,k);
    if(m==0)
        return B[j+k-1];
    if(k==1)
        return Math.min(A[i],B[j]);
    int posA = Math.min(k/2,m);
    int posB = k-posA;
    if(A[i+posA-1]==B[j+posB-1])
        return A[i+posA-1];
    else if(A[i+posA-1]<B[j+posB-1])
        return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);
    else
        return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);
}

实现中还是有些细节要注意的，比如有时候剩下的数不足k/2个，那么就得剩下的，而另一个数组则需要多取一些数。但是由于这种情况发生的时候，不是把一个数组全部读完，就是可以切除k/2个数，所以不会影响算法的复杂度。
这道题的优化算法主要是由order statistics派生而来，原型应该是求topK的算法，这个问题是非常经典的问题，一般有两种解法，一种是用quick select(快速排序的subroutine),另一种是用heap。 复杂度是差不多的，有兴趣可以搜一下，网上资料很多，topK问题在海量数据处理中也是一个非常经典的问题，所以还是要重视。

3Sum -- LeetCode

原题链接: https://oj.leetcode.com/problems/3sum/
这道题是Two Sum的扩展，brute force时间复杂度为O(n^3), 对每三个数进行比较。这道题和Two Sum有所不同，使用哈希表的解法并不是很方便，因为结果数组中元素可能重复，如果不排序对于重复的处理将会比较麻烦，因此这道题一般使用排序之后夹逼的方法，总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n),代码如下：

public ArrayList<ArrayList<Integer>> threeSum(int[] num)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null || num.length<=2)
        return res;
    Arrays.sort(num);
    for(int i=num.length-1;i>=2;i--)
    {
        if(i<num.length-1 && num[i]==num[i+1])
            continue;
         ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,-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>>();
    if(num==null || num.length<=1)
        return res;
    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;
}

注意，在这里为了避免重复结果，对于已经判断过的数会skip掉，这也是排序带来的方便。 这道题考察的点其实和Two Sum差不多，Two Sum是3Sum的一个subroutine, 不过更加综合一些，实现上更加全面，需要注意细节，面试中比较常见的一道题。此题更加复杂的扩展是4Sum，请参见4Sum -- LeetCode.

Two Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/two-sum/
这是一道非常经典的题目，brute force时间复杂度为O(n^2), 对每一对pair两两比较。 优化的方法一般有两种，第一种是用哈希表，时间复杂度为O(n),同时空间复杂度也是O(n),代码如下：

public int[] twoSum(int[] numbers, int target) {
    int[] res = new int[2];
    if(numbers==null || numbers.length<2)
        return null;
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i=0;i<numbers.length;i++)
    {
        if(map.containsKey(target-numbers[i]))
        {
            res[0]=map.get(target-numbers[i])+1;
            res[1]=i+1;
            return res;
        }
        map.put(numbers[i],i);
    }
    return null;
}

第二种解法是先对数组进行排序，然后使用夹逼的方法找出满足条件的pair，原理是因为数组是有序的，那么假设当前结果比target大，那么左端序号右移只会使两个数的和更大，反之亦然。所以每次只会有一个选择，从而实现线性就可以求出结果。该算法的时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度取决于排序算法。代码如下：

public int[] twoSum(int[] numbers, int target) {
    int[] res = new int[2];
    if(numbers==null || numbers.length<2)
        return null;
    Arrays.sort(numbers);
    int l = 0;
    int r = numbers.length-1;
    while(l<r)
    {
        if(numbers[l]+numbers[r]==target)
        {
            res[0] = number[l];
            res[1] = number[r];
            return res;
        }
        else if(numbers[l]+numbers[r]>target)
        {
            r--;
        }
        else
        {
            l++;
        }
    }
    return null;
}

注意，在这里，输出结果改成了满足相加等于target的两个数，而不是他们的index。因为要排序，如果要输出index，需要对原来的数的index进行记录，方法是构造一个数据结构，包含数字的值和index，然后排序。所以从这个角度来看，这道题第二种解法并没有第一种解法好，空间也是O(n). 在LeetCode原题中是假设结果有且仅有一个的，一般来说面试时会要求出所有的结果，这个时候会涉及到重复pair的处理，相关的内容会在3Sum那道题目中涉及到，请参见3Sum -- LeetCode.

Maximum Depth of Binary Tree -- LeetCode

原题链接：http://oj.leetcode.com/problems/maximum-depth-of-binary-tree/
这是一道比较简单的树的题目，可以有递归和非递归的解法，递归思路简单，返回左子树或者右子树中大的深度加1，作为自己的深度即可，代码如下：

public int maxDepth(TreeNode root) {
    if(root == null)
        return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

非递归解法一般采用层序遍历(相当于图的BFS），因为如果使用其他遍历方式也需要同样的复杂度O(n). 层序遍历理解上直观一些，维护到最后的level便是树的深度。代码如下：

public int maxDepth(TreeNode root) {
    if(root == null)
        return 0;
    int level = 0;
    LinkedList queue = new LinkedList();
    queue.add(root);
    int curNum = 1; //num of nodes left in current level
    int nextNum = 0; //num of nodes in next level
    while(!queue.isEmpty())
    {
        TreeNode n = queue.poll();
        curNum--;
        if(n.left!=null)
        {
            queue.add(n.left);
            nextNum++;
        }
        if(n.right!=null)
        {
            queue.add(n.right);
            nextNum++;
        }
        if(curNum == 0)
        {
            curNum = nextNum;
            nextNum = 0;
            level++;
        }
    }
    return level;
}

总体来说我觉得这道题可以考核树的数据结构，也可以看看对递归和非递归的理解。相关的扩展可以是Minimum Depth of Binary Tree.