LeetCode 题目解答——Medium 部分（下）

[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。

这是 LeetCode 题目 Medium 难度部分中的下半部分，表格中的 Acceptance 是 LeetCode 网上拷贝下来的的数据。这些完成以后，就只剩 Hard 部分了。欢迎讨论。

Multiply Strings

【题目】Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

【解答】按照自己在草稿上计算多位数乘以多位数的的方法那样计算，这种题目要一次性做对还是有难度的。考虑好进位，还有为 num1 或者 num2 为零的情况。对了，这里面涉及到反复给字符串的前面添加字符（prepend），如果是 append 的话我可以用 StringBuilder 提高效率，但是 prepend 的话，我找不到一个好的办法（StringBuilder 的 insert(0, “xxx”) 性能上看和普通的字符串拼接一样不可取，都是新建字符串然后 System.arrayCopy() 的）。如果你知道请告诉我。

public class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2))
            return "0";

        String res = "";
        for (int i=num1.length()-1; i>=0; i--) {
            String sum = "";
            int carry = 0;
            int n1 = num1.charAt(i)-'0';

            for (int j=num2.length()-1; j>=0; j--) {
                int n2 = num2.charAt(j)-'0';

                int product = n1*n2 + carry;
                String digit = product%10 + "";

                carry = product/10;

                sum = digit + sum;
            }

            if (carry>0)
                sum = carry + sum;

            res = add(res, sum, (num1.length()-1)-i);
        }

        return res;
    }

    private String add(String total, String num, int pos) {
        int carry = 0;
        String res = "";
        for (int i=total.length()-1, j=num.length()-1 + pos; i>=0 || j>=0; i--, j--) {
            int n1 = 0;
            if (i>=0)
                n1 = total.charAt(i) - '0';

            int n2 = 0;
            if (j>=0 && j<num.length())
                n2 = num.charAt(j) - '0';

            int sum = n1+n2+carry;
            res = (sum%10) + res;
            carry = sum/10;
        }

        if (carry>0)
            res = carry + res;

        return res;
    }
}

Sum Root to Leaf Numbers

【题目】Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

【解答】没什么可说的：

public class Solution {
    public int sumNumbers(TreeNode root) {
        if (null==root)
            return 0;

        List<String> list = getPathSum(root);
        int sum = 0;
        for (String num : list) {
            sum += Integer.parseInt(num);
        }

        return sum;
    }

    private List<String> getPathSum(TreeNode root) {
        List<String> list = new ArrayList<>();

        if (root.left==null && root.right==null)
            list.add(root.val+"");

        if (root.left!=null)
            for (String num : getPathSum(root.left)) {
                list.add(root.val + num);
            }

        if (root.right!=null)
            for (String num : getPathSum(root.right)) {
                list.add(root.val + num);
            }

        return list;
    }
}

Subsets II

【题目】Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

【解答】和 Subsets 那道题差不多，唯一的区别是源数组有可能有重复的数字，我在那道题的基础上增加了这样的逻辑：比如 num 为 [1,2,2,2]，在某一时刻，list 里面为 [ [], [1], [2], [1, 2], [1, 2, 2]] 的时候，再 clone 并 append 后面一个 2 进 list 的时候，需要找前面连续的 2 出现次数最多的那个，即 [1,2,2]，而其它元素不变。

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);

        ArrayList<List<Integer>> list = new ArrayList<>();
        List<Integer> l1= new ArrayList<>();
        list.add(l1);

        int recent = Integer.MAX_VALUE;
        int dupCount = 0;
        for (int s : num) {

            ArrayList<List<Integer>> newList = new ArrayList<>();
            if (recent==s) {
                for (List<Integer> l : list) {
                    int count = 0;
                    for (int i=l.size()-1; i>=0; i--) {
                        if (l.get(i)==s) {
                            count++;

                            if (count==dupCount)
                                newList.add(new ArrayList<Integer>(l));
                        }
                        else {
                            break;
                        }
                    }
                }

                dupCount++;
            }
            else {
                // don't use list.clone()
                for (List<Integer> l : list) {
                    newList.add(new ArrayList<Integer>(l));
                }

                recent = s;
                dupCount = 1;
            }

            for (List<Integer> l : newList) {
                l.add(s);
            }

            list.addAll(newList);
        }

        return list;
    }
}

Next Permutation

【题目】Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

【解答】这道题题目让我理解了好半天。给你一串数，要找到下一个排列，比这个排列大，并且恰好比这个排列大，就是说对于原排列和新排列没法找到另一个排列插在这二者之间。比如 1,2,3，值是 123，那么下一个排列就是 132，你没法找到一个居于 123 和 132 之间的排列。

题意搞清楚以后，问题就好办了：

1. 从最右边那一位开始往左寻找，找到的数应该都是依次增大的，如果发现这个递增的规律被打破，这就说明这个数 num[a] 需要和它当前右侧的数中 “比它大的最小数”num[b] 交换。以 1,4,3,2 为例，从右往左找，从 2 到 3，从 3 到 4 都是递增的，但是 1 出现的时候，这个递增关系被打破，于是在 1 的右边的比 1 大的数中，寻找一个最小值，在这里是 2。
2. 交换 num[a] 和 num[b]，这就变成了 2,4,3,1。
3. 对于位置 a 右侧的数按照递增的顺序重排列，变成了 2,1,3,4。

注意特殊情况的处理，对于整个排列从右到左是严格递增的情况，比如 4,3,2,1，它的下一个排列是从右到左严格递减的序列，1,2,3,4，这一点起初我给忽略了，题目里面其实有写：“it must rearrange it as the lowest possible order (ie, sorted in ascending order)”。

public class Solution {
    public void nextPermutation(int[] num) {

        for (int i=num.length-1; i>0; i--) {
            if (num[i-1]<num[i]) {

                // find out the minimum number which is larger than num[i-1]
                int min = Integer.MAX_VALUE;
                int pos = -1;

                for (int j=i; j<num.length; j++) {
                    if (num[i-1]<num[j] && num[j]<min) {
                        min = num[j];
                        pos = j;
                    }
                }

                // exchange
                num[i-1] = num[i-1]^num[pos];
                num[pos] = num[i-1]^num[pos];
                num[i-1] = num[i-1]^num[pos];

                // sort, make the sub array [i, num.length) increasing
                Arrays.sort(num, i, num.length);

                return;
            }
        }

        Arrays.sort(num);
        return;

    }
}

3Sum Closest

【题目】Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

【解答】先排序，然后左右各一指针，在 sum 小于目标值的时候左指针向右走，在 sum 大于目标值的时候右指针向左走。

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);

        int closest = java.lang.Integer.MAX_VALUE;
        int sumWhenClosest = 0;
        // i, j, k, when i is determined, the sum = f(j,k)
        for (int i=0; i<num.length; i++) {
            // j traverses from left to right, k traverses from right to left
            int j=i+1;
            int k=num.length-1;

            // j can only move towards right and k can only move towards left
            while (j<k){
                int sum = num[i] + num[j] + num[k];
                int newClosest = java.lang.Math.abs(sum-target);
                if (newClosest<closest) {
                    closest = newClosest;
                    sumWhenClosest = sum;
                }

                if (sum==target)
                    return target;

                if (sum<target)
                    k--;
                else
                    j++;
            } // while
        } // for

        return sumWhenClosest;
    }
}

Palindrome Partitioning

【题目】

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

【解答】给定一字符串，寻找各种回文串的组合。大致思路是，对于字符串的任一子串（给定了 start 和 end 位置，子串即为 [start,end) 区间的串），对于 i∈(start,i]，判定 [start,i) 区间的子串是否为回文，如果是回文，那么递归寻找 [i,end) 的所有组合可能。写完以后，我觉得如果执行的时候超时，还可以优化成 DP，用一张二维表记录中间结果以避免重复计算，不过那是用空间换时间了，既然已经 AC 就不再优化。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        if (null==s||"".equals(s))
            return list;

        return partition(s, 0, s.length());
    }

    private List<List<String>> partition(String s, int start, int end) {
        List<List<String>> list = new ArrayList<>();

        if (isPalindrome(s, start, end)) {
            List<String> l = new ArrayList<>();
            l.add(s.substring(start, end));

            list.add(l);
        }

        if (end-start==1) {
            return list;
        }

        for (int i=start+1; i<end; i++) {
            if (isPalindrome(s, start, i)) {
                List<List<String>> ls = partition(s, i, end);

                for (List<String> l : ls) {
                    l.add(0, s.substring(start, i));
                }

                list.addAll(ls);
            }
        }

        return list;
    }

    private boolean isPalindrome(String s, int start, int end) {
        for (int i=start, j=end-1; j>i; j--,i++) {
            if (s.charAt(i)!=s.charAt(j))
                return false;
        }

        return true;
    }
}

Subsets

【题目】Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

【解答】题目应该说是很简单的，但是我第一遍用递归做，提示超时，第二遍我用循环做，还是超时。我就觉得奇怪，后来发现，在创建新 list 的时候，不要使用 ArrayList.clone() 方法，而是循环并调用参数为 Collection 的构造器：public ArrayList(Collection<? extends E> paramCollection)。

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        Arrays.sort(S);

        ArrayList<List<Integer>> list = new ArrayList<>();
        List<Integer> l1= new ArrayList<>();
        list.add(l1);

        for (int s : S) {

            // don't call list.clone()
            ArrayList<List<Integer>> newList = new ArrayList<>();
            for (List<Integer> l : list) {
                newList.add(new ArrayList<Integer>(l));
            }

            for (List<Integer> l : newList) {
                l.add(s);
            }

            list.addAll(newList);
        }

        return list;
    }
}

Partition List

【题目】Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

【解答】看清楚题意，是要把比 x 小的数搬到不小于 x 的数的左边去。两个指针，left.next 为要搬过去的位置，right.next 为被搬的数。增加一个守卫节点 fakeHead，这样就可以比较容易地处理要考虑的位置出现在头部的特殊情况。

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
        fakeHead.next = head;

        ListNode left = fakeHead;
        while (left.next!=null && left.next.val<x)
            left = left.next;

        ListNode right = left.next;
        while (right!=null && right.next!=null) {
            if (right.next.val<x) {
                move(left, right);
                left = left.next;
            }
            else {
                right = right.next;
            }
        }

        return fakeHead.next;
    }

    /**
     * move right.next to left.next
     */
    private void move(ListNode left, ListNode right) {
        ListNode target = right.next;
        right.next = target.next;

        ListNode leftNext = left.next;
        left.next = target;
        target.next = leftNext;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

【题目】Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

【解答】初看没啥头绪，不过草稿纸上随便画了一个简单的二叉树：1 / 2 3 / 4 5 6 7，

它的中序遍历是：4 2 5 1 6 3 7

它的后序遍历是：4 5 2 6 7 3 1

可以获知的是，对于这样的情形下，根节点是后序遍历序列的最后一个数——1，既然题中说没有重复的数，那么把这个 1 放到中序遍历的序列中去找，找到了以后，1 的左侧的子序列 [4,2,5] 和后序遍历相应的前三个数 [4,5,2] 就可以继续构造左子树，而 1 的右侧的子序列 [6,3,7] 和后序遍历的接下去的三个数 [6,7,3] 可以继续构造右子树。

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode fakeRoot = new TreeNode(0);
        buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, fakeRoot, true);
        return fakeRoot.left;
    }

    private void buildTree(int[] inorder, int istart, int iend, int[] postorder, int pstart, int pend, TreeNode parent, boolean leftOrRight) {
        if (iend<istart)
            return;

        // root == postorder[pend]
        for (int i=istart; i<=iend; i++) {
            if (postorder[pend]==inorder[i]) {
                TreeNode root = new TreeNode(postorder[pend]);
                if (leftOrRight)
                    parent.left = root;
                else
                    parent.right = root;

                buildTree(inorder, istart, i-1, postorder, pstart, pstart + (i-1-istart), root, true);
                buildTree(inorder, i+1, iend, postorder, pend-1 - (iend-i-1), pend - 1, root, false);
            }
        }
    }
}

Construct Binary Tree from Preorder and Inorder Traversal

【题目】Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

【解答】思路和前面那道题一致，不罗嗦了。前序遍历数组的第一个元素就是根。

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend) {
        if (pstart>pend)
            return null;

        for (int i=istart; i<=iend; i++) {
            if (inorder[i]==preorder[pstart]) {
                TreeNode root = new TreeNode(inorder[i]);
                root.left = buildTree(preorder, pstart+1, pstart+1+(i-1-istart), inorder, istart, i-1);
                root.right = buildTree(preorder, pend-(iend-i-1), pend, inorder, i+1, iend);

                return root;
            }
        }

        return null;
    }
}

Combinations

【题目】Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

【解答】数学归纳法，对于每一种组合 f(n,k)，都有两种可能组成（注意递归出口，其实只有一个，即 k 到 0 的时候，下面这个写得还是啰嗦了一点）：

• n 没有被选中，即 f(n-1,k)，这种情况下需要 n>k；
• n 被选中，即 f(n-1,k-1)。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if (n==0 || k==0) { // for recursion exit 2
            List<Integer> list = new java.util.ArrayList<>();
            List<List<Integer>> total = new java.util.ArrayList<>();
            total.add(list);
            return total;
        } else if (n==k) { // for recursion exit 1
            List<Integer> list = new java.util.ArrayList<>();
            for (int i=1; i<=n; i++) {
                list.add(i);
            }
            List<List<Integer>> total = new java.util.ArrayList<>();
            total.add(list);
            return total;
        } else {
            // case 1: last element is not selected => recursion exit 1
            List<List<Integer>> subList1 = combine(n-1, k);

            // case 2: last element (n) is seleced, so pick k-1 elements out from n-1 totals => recursion exit 2
            List<List<Integer>> subList2 = combine(n-1, k-1);
            // then add the last element
            for (List<Integer> l : subList2) {
                l.add(n);
                subList1.add(l); // merge into subList1
            }

            return subList1;
        }
    }

}

Combination Sum II

【题目】Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,

A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6]

【解答】看起来和 “Combination Sum” 那道题差不多，也是要回溯法，但还是有区别的——主要在于去重（比如 [2,2,2] 这样的数组，如果每次取一个元素，那么取第 0、2 个元素和取第 0、1 个元素分别形成的 list 都是 [2,2]，这就造成了重复），每次递归调用在从 pos 开始的连续相同的元素出现时，只有第一次出现的那个才被保留。另外，还有一个小的优化，在于递归调用 com 方法传递 list 参数的时候，我并不是每次都创建一个全新的 ArrayList 传递，而是重用传入的 list，add(num[i]) 改变 list 的内容，但是递归调用 com 方法以后，恢复现场，删掉刚才加进去的 num[i]。

public class Solution {
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);

        List<List<Integer>> total = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        total.add(l);

        return com(total, num, target, 0);
    }

    public List<List<Integer>> com(List<List<Integer>> list, int[] num, int target, int pos){
        List<List<Integer>> total = new ArrayList<>();
        if (target==0) {
            for(List<Integer> l : list) {
                List<Integer> nl = new ArrayList<Integer>(l);
                total.add(nl);
            }
            return total;
        }

        for (int i=pos; i<num.length; i++) {
            if (num[i]>target)
                break;

            if(i==pos || num[i]!=num[i-1]) { // dedup
                for (List<Integer> l:list)
                    l.add(num[i]);

                total.addAll(com(list, num, target-num[i], i+1));

                for (List<Integer> l:list)
                    l.remove(l.size()-1);
            }
        }

        return total;
    }
}

Path Sum II

【题目】Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

【解答】其实也没什么可说的。如果题目里面的数都是正数的话，在遍历的过程当中有一些已经大于目标值的 list 就可以抛弃了，不需要等到递归的最后再判断。

 public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> ret = new ArrayList<>();
        if (root==null)
            return ret;

        List<List<Integer>> list = pathSum(root);

        for (List<Integer> l : list) {
            int total = 0;
            for (int num : l) {
                total += num;
            }

            if (total==sum)
                ret.add(l);
        }

        return ret;
    }

    private List<List<Integer>> pathSum(TreeNode root) {
        List<List<Integer>> paths = new ArrayList<>();

        if (root.left!=null) {
            List<List<Integer>> list = pathSum(root.left);
            for (List<Integer> l : list) {
                l.add(0, root.val);
            }
            paths.addAll(list);
        }

        if (root.right!=null) {
            List<List<Integer>> list = pathSum(root.right);
            for (List<Integer> l : list) {
                l.add(0, root.val);
            }
            paths.addAll(list);
        }

        if (root.left==null && root.right==null) {
            List<Integer> item = new ArrayList<>();
            item.add(root.val);
            paths.add(item);
        }

        return paths;
    }
}

Permutation Sequence

【题目】The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

【解答】对于 n，在某一个 permutation 的最高位确定的时候，下面 n-1 位的组合可能是 (n-1)! 种，所以可以用除法从最高位开始依次确定每一位的数值。

public class Solution {
    public String getPermutation(int n, int k) {

        ArrayList<Integer> list = new ArrayList<>();
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            list.add(i);
            factorial *= i;
        }

        // !!!
        k = k-1;

        StringBuilder sb = new StringBuilder();

        for (int i = n; i > 0; i--) {
            factorial = factorial / i;
            int index = k / factorial;

            sb.append(list.get(index));
            list.remove(index);

            k = k % factorial;
        }

        return sb.toString();
    }
}

Permutations

【题目】Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

【解答】这题似乎没啥大意思，就是循环遍历到所有情况就行了。

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        List<Integer> src = new ArrayList<>();
        for (int i=0; i<num.length; i++) {
            src.add(num[i]);
        }

        List<Integer> l = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        list.add(l);

        return permute(list, src);
    }

    private List<List<Integer>> permute(List<List<Integer>> list, List<Integer> src) {
        if (src.isEmpty())
            return list;

        List<List<Integer>> total = new ArrayList<>();

        for (int i=0; i<src.size(); i++) {
            int num = src.get(i);
            List<Integer> newSrc = new ArrayList<>(src);
            newSrc.remove(i);
            List<List<Integer>> newList = new ArrayList<>();
            for (List<Integer> l : list) {
                List<Integer> copy = new ArrayList<Integer>(l);
                copy.add(num);
                newList.add(copy);
            }

            total.addAll(permute(newList, newSrc));
        }

        return total;
    }
}

Sqrt(x)

【题目】Implement int sqrt(int x).

Compute and return the square root of x.

【解答】基本上是根据二分搜索的办法求解，但是有这么两个需要注意的地方：

• 使用 long 是因为考虑可能溢出的情况；
• 这题有点恶心的地方在于，要求返回 int 型，比如当 x 是 2 的时候，要求返回 1，所以 while (min <= max) 这行就是起这个作用的，当 min==max 的时候，并不意味着找到这个数了，如果不符合条件（比如 x=2 的时候，第二遍循环后 min 会变成 2，max 会变成 1），这时候离开了 while，必须返回 max。

public class Solution {
    public int sqrt(int x) {
        long min = 0;
        long max = x / 2 + 1;

        while (min <= max)
        {
            long mid = (min + max) / 2;
            long product = mid * mid;

            if (product == x)
                return (int)mid;
            else if (product < x)
                min = mid + 1;
            else
                max = mid - 1;
        }

        return (int)max;
    }
}

后来知道有种 “牛顿迭代法” 可以用来比二分查找更高效地求解平方根。

Combination Sum

【题目】Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,

A solution set is: 
[7] 
[2, 2, 3]

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);

        List<List<Integer>> list = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        list.add(l);

        return combinationSum(list, candidates, target, 0);
    }

    private List<List<Integer>> combinationSum(List<List<Integer>> list, int[] candidates, int target, int pos) {
        List<List<Integer>> total = new ArrayList<>();
        if (pos==candidates.length) {
            if (target==0)
                return list;
            return total;
        }

        for (int i=0; i*candidates[pos]<=target; i++) {
            List<List<Integer>> newList = new ArrayList<>();
            for (List<Integer>l : list) {
                List<Integer> nl = new ArrayList<Integer>(l);
                for (int j=1; j<=i; j++)
                    nl.add(candidates[pos]);
                newList.add(nl);
            }
            total.addAll(combinationSum(newList, candidates, target-i*candidates[pos], pos+1));
        }

        return total;
    }
}

Populating Next Right Pointers in Each Node

【题目】Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,

Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

【解答】一层一层往下建立 next 关系：

public class Solution {
    public void connect(TreeLinkNode root) {
        traverse (root, null);
    }

    public void traverse (TreeLinkNode node, TreeLinkNode next) {
        if(null==node)
            return;

        node.next = next;

        // left child
        traverse (node.left, node.right);

        // right child
        if (null==node.next)
            traverse (node.right, null);
        else
            traverse (node.right, node.next.left);
    }
}

Spiral Matrix II

【题目】Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

【解答】这道题和 “Spiral Matrix” 本质上没啥区别，思路也是几乎一模一样的，不提了。

public class Solution {
    private static final int UP = 1;
    private static final int DOWN = 2;
    private static final int LEFT = 3;
    private static final int RIGHT = 4;

    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        if (matrix.length==0 || matrix[0].length==0)
            return matrix;

        int direction = RIGHT;

        int boundUp = 0;
        int boundDown = matrix.length;
        int boundLeft = -1;
        int boundRight = matrix[0].length;

        int x=0;
        int y=0;

        int i=1;

        while (boundUp<boundDown && boundLeft<boundRight) {
            matrix[y][x] = i++;

            switch (direction) {
                case RIGHT:
                    if (x<boundRight-1) {
                        x++;
                    } else if (y<boundDown-1) {
                        y++;
                        direction = DOWN;
                        boundRight--;
                    } else {
                        return matrix;
                    }
                    break;
                case DOWN:
                    if (y<boundDown-1) {
                        y++;
                    } else if (x>boundLeft+1) {
                        x--;
                        direction = LEFT;
                        boundDown--;
                    } else {
                        return matrix;
                    }
                    break;
                case LEFT:
                    if (x>boundLeft+1) {
                        x--;
                    } else if (y>boundUp+1) {
                        y--;
                        direction = UP;
                        boundLeft++;
                    } else {
                        return matrix;
                    }
                    break;
                case UP:
                    if (y>boundUp+1) {
                        y--;
                    } else if (x<boundRight-1) {
                        x++;
                        direction = RIGHT;
                        boundUp++;
                    } else {
                        return matrix;
                    }
                    break;
            }
        }

        return matrix;
    }
}

Pow(x, n)

【题目】Implement pow(x, n).

【解答】初看起来挺简单的题目，但是有陷阱，要一遍做对其实挺不容易的：

• 最开始我考虑用一个数组来存放以往计算过的记录，但是对于临界的 case，数组下标达到了 int 型的上限，而且实际上这个数组里面大部分元素都是空的，利用率很低，于是改成 HashMap；
• 为了避免溢出（溢出的原因是当 n 为 Integer.MIN_VALUE 的时候，它是没法取相反值的，一取就溢出了），用 long 型来作为 key，而不是 int；
• 需要考虑 n 为负数的情况。

public class Solution {
    public double pow(double x, int n) {
        long m = (long)n;
        boolean negative = false;
        if (m<=0) {
            m = -m;
            negative = true;
        }
        Map<Long, Double> map = new HashMap<>();
        double ret = pow(x, m, map);

        if (negative)
            return 1/ret;

        return ret;
    }

    private double pow(double x, long n, Map<Long, Double> map) {
        if (n==0)
            return 1;
        if (n==1)
            return x;

        if (map.containsKey(n))
            return map.get(n);

        double ret = pow(x, n/2, map) * pow(x, (n-n/2), map);
        map.put(n, ret);

        return ret;
    }
}

Spiral Matrix

【题目】Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

【解答】就是状态机，根据每走一步前的状态决定下一步应该怎么走。值得小心的是，如果按照数组的行列习惯 matrix[x][y] 表示的是第 x 行，第 y 列；如果按照坐标轴的习惯，x 轴是横轴，表示的是第几列，y 轴是纵轴，表示的是第几行，所以 x 行 y 列应该表示为 matrix[y][x]。选择其中一种，别搞乱了就好。这里我选择了后者。

public class Solution {
    private static final int UP = 1;
    private static final int DOWN = 2;
    private static final int LEFT = 3;
    private static final int RIGHT = 4;

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix.length==0 || matrix[0].length==0)
            return list;

        int direction = RIGHT;

        int boundUp = 0;
        int boundDown = matrix.length;
        int boundLeft = -1;
        int boundRight = matrix[0].length;

        int x=0;
        int y=0;

        while (boundUp<boundDown && boundLeft<boundRight) {
            list.add(matrix[y][x]);

            switch (direction) {
                case RIGHT:
                    if (x<boundRight-1) {
                        x++;
                    } else if (y<boundDown-1) {
                        y++;
                        direction = DOWN;
                        boundRight--;
                    } else {
                        return list;
                    }
                    break;
                case DOWN:
                    if (y<boundDown-1) {
                        y++;
                    } else if (x>boundLeft+1) {
                        x--;
                        direction = LEFT;
                        boundDown--;
                    } else {
                        return list;
                    }
                    break;
                case LEFT:
                    if (x>boundLeft+1) {
                        x--;
                    } else if (y>boundUp+1) {
                        y--;
                        direction = UP;
                        boundLeft++;
                    } else {
                        return list;
                    }
                    break;
                case UP:
                    if (y>boundUp+1) {
                        y--;
                    } else if (x<boundRight-1) {
                        x++;
                        direction = RIGHT;
                        boundUp++;
                    } else {
                        return list;
                    }
                    break;
            }
        }

        return list;
    }
}

Sort List

【题目】Sort a linked list in O(n log n) time using constant space complexity.

【解答】要 n*logn 复杂度的排序，我最开始尝试用快排去解，但是很快遇到问题，原因在于这是个 linked list，快排经常需要寻找一个节点的前一个节点，不是不能做，而是很麻烦，自己做做就烦了，干脆换成归并排序，这就很容易完成了，因为归并排序不需要往回走。不过，归并排序需要不断地寻找中间切分链表的节点，利用快慢双指针来寻找这样的一个节点。另外，在归并的时候，建立一个 fake head，让代码简单一些，不需要处理头部的特殊情况。

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head==null || head.next==null)
            return head;

        ListNode fast = head, slow = head;
        while (fast.next!=null && fast.next.next!=null)
        {
            fast = fast.next.next; // 2 steps
            slow = slow.next; // 1 step
        }

        // split
        fast = slow;
        slow = slow.next;
        fast.next = null;

        fast = sortList(head);
        slow = sortList(slow);

        return merge(fast, slow);
    }

    private ListNode merge(ListNode h1, ListNode h2) {
        if(h1==null)
            return h2;
        if(h2==null)
            return h1;

        // fake head
        ListNode head = new ListNode(0);
        ListNode node = head;

        while (h1!=null && h2!=null)
        {
            if(h1.val < h2.val)
            {
                node.next = h1;
                h1 = h1.next;
            } else {
                node.next = h2;
                h2 = h2.next;
            }
            node = node.next;
        }

        if (h1!=null)
            node.next = h1;
        else if (h2!=null)
            node.next = h2;

        return head.next;
    }
}

Clone Graph

【题目】

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

【解答】这是一种存在环的图，我的办法是把整个图的拷贝拆成两步，第一步创建节点，第二步才是建立联系。为了避免递归导致栈溢出，要严格避免在递归传递的过程中出现中间状态，比如说，buildRelation 那一步，在所有的关联关系给当前节点添加完成之前，不可以执行递归调用的逻辑。

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (null==node)
            return null;

        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        buildNodes(node, map);
        buildRelation(node, map);

        return map.get(node.label);
    }

    private void buildNodes(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
        if (!map.containsKey(node.label)) {
            UndirectedGraphNode n = new UndirectedGraphNode(node.label);
            map.put(node.label, n);
        }

        for (UndirectedGraphNode ne : node.neighbors) {
            if (!map.containsKey(ne.label)) {
                map.put(ne.label, new UndirectedGraphNode(ne.label));
                buildNodes(ne, map);
            }
        }
    }

    private void buildRelation(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
        UndirectedGraphNode n = map.get(node.label);

        if(node.neighbors.size()!=n.neighbors.size()) {
            for (UndirectedGraphNode ne : node.neighbors) {
                n.neighbors.add(map.get(ne.label));
            }

            for (UndirectedGraphNode ne : node.neighbors) {
                buildRelation(ne, map);
            }
        }

    }
}

Remove Duplicates from Sorted Array II

【题目】Follow up for “Remove Duplicates”:

What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

【解答】如下。不过我的代码 arraycopy 拷贝的总元素数目多，这一步其实可以优化，使得所有元素至多只被拷贝一次。

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length<3)
            return A.length;

        int slow = 0;
        int fast = 1;

        int dup = 1;
        int len = A.length;

        while (fast<len) {
            if (A[slow]==A[fast]) {
                dup++;
                fast++;
            } else {
                if (dup>2) {
                    System.arraycopy(A, fast, A, slow+2, len-fast);
                    len = len - (fast-slow) + 2;

                    slow = slow + 1;
                    fast = slow + 1;
                } else {
                    slow = fast;
                    fast++;
                }

                dup = 1;
            }
        }

        if (dup>2) {
            len = len - (fast-slow) + 2;
        }

        return len;
    }
}

Sort Colors

【题目】Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

【解答】两个指针，先交换红色的，再交换白色的，只需要常数的额外空间。

public class Solution {
    private static final int RED = 0;
    private static final int WHITE = 1;
    private static final int BLUE = 2;

    public void sortColors(int[] A) {
        if (A.length<2)
            return;

        int i=0, j=1;
        // RED
        while (j<A.length) {
            if (A[i]!=RED) {
                if (A[j]==RED) {
                    // swap
                    int temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;

                    i++;
                    j++;
                } else {
                    j++;
                }
            } else {
                i++;
                if (i==j)
                    j++;
            }
        }

        // WHITE
        j=i+1;
        while (j<A.length) {
            if (A[i]!=WHITE) {
                if (A[j]==WHITE) {
                    // swap
                    int temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;

                    i++;
                    j++;
                }
                else {
                    j++;
                }
            } else {
                i++;
                if (i==j)
                    j++;
            }
        }

    }
}

Remove Duplicates from Sorted List II

【题目】Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

【解答】快慢两个指针，慢指针占据重复子串的前面那个位置，快指针占据重复子串的最后一位，所以每次删掉重复子串都是 slow.next = fast.next。注意考虑其中 fast.next==null 的特殊情况。另外，引入一个 fake head 可以帮助简化问题。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode fake = new ListNode(Integer.MIN_VALUE);
        fake.next = head;

        ListNode slow = fake;
        ListNode fast = fake.next;

        while (fast != null) {
            if (slow.next != fast && slow.next.val == fast.val
                    && (fast.next == null || fast.val != fast.next.val)) {
                slow.next = fast.next;
                fast = slow.next;
            } else {
                if (fast.next == null || fast.val != fast.next.val)
                    slow = fast;
                fast = fast.next;
            }
        }

        return fake.next;
    }
}

Binary Tree Zigzag Level Order Traversal

【题目】Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

【解答】锯齿形一层一层输出。没什么难度，不过注意容易出错的地方，一个是每一层输出的方向，还有一个是递归出口。

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (null==root)
            return new ArrayList<List<Integer>>();

        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);

        return traverse(nodes, true);
    }

    private List<List<Integer>> traverse(List<TreeNode> nodes, boolean leftToRight) {

        List<List<Integer>> total = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        if (leftToRight) {
            for (TreeNode n : nodes) {
                l.add(n.val);
            }
        } else {
            for (int i=nodes.size()-1; i>=0; i--) {
                l.add(nodes.get(i).val);
            }
        }
        total.add(l);

        List<TreeNode> ns = new ArrayList<>();
        for (TreeNode n : nodes) {
            if (n.left!=null)
                ns.add(n.left);
            if (n.right!=null)
                ns.add(n.right);
        }
        if (!ns.isEmpty())
            total.addAll(traverse(ns, !leftToRight));

        return total;
    }
}

Binary Tree Preorder Traversal

【题目】Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

【解答】无论是先序、中序还是后序遍历，如果是递归，都很简单：

public class Solution {
    private List<Integer> array = new java.util.ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        traverse(root);
        return array;
    }

    private void traverse(TreeNode node){
        if(node==null)
            return;

        array.add(node.val);
        traverse(node.left);
        traverse(node.right);
    }
}

但是如果是循环，那么先序和中序遍历也比较简单（后序遍历就会比较难）：

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root==null)
            return list;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);

            if (node.right!=null)
                stack.push(node.right);

            if (node.left!=null)
                stack.push(node.left);
        }

        return list;
    }
}

Reorder List

【题目】Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

【解答】先用一个 stack 存放从后往前的节点。然后一条路线是从原链表的 head 开始往后遍历，每次元素为 cur，另一条路线是从 stack 里面 pop 出元素 n，每次每条路线各取一个节点放到一起。注意处理特殊情形，在链表结点为奇数个时，会出现 cur==n；在链表节点为偶数时，当次迭代执行完毕后 cur.next==n。

public class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur!=null) {
            stack.push(cur);
            cur = cur.next;
        }

        cur = head;
        while (cur!=null) {
            ListNode n = stack.pop();
            if (cur!=n) {
                ListNode temp = cur;
                cur = cur.next;
                temp.next = n;
                n.next = cur;
                if (cur.next==n) {
                    cur.next = null;
                    break;
                }
            } else {
                cur.next = null;
                break;
            }
        }
    }
}

Restore IP Addresses

【题目】Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

【解答】回溯法递归求解。这里有一个陷阱，就是像 101011 这样的 case，是不能切分成 1.01.0.11 这样的，因为第二个块是 01，是需要去除的情形。所以下面代码中排除掉 subStr 以 “0” 开头但是长度又大于 1 的分支。

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        return restore(new int[0], s);
    }

    private List<String> restore(int[] tokens, String rest) {
        List<String> total = new ArrayList<>();
        if (tokens.length==4) {
            if ("".equals(rest)) {
                String ip = "";
                for (int i=0; i<4; i++) {
                    if (!"".equals(ip))
                        ip += '.';
                    ip += String.valueOf(tokens[i]);
                }
                total.add(ip);
            }

            return total;
        }

        for (int i=1; i<=3 && i<=rest.length(); i++) {
            String subStr = rest.substring(0, i);
            int sub = Integer.parseInt(subStr);
            if ((subStr.startsWith("0") && i>1) || sub>255)
                break;

            int[] ts = new int[tokens.length+1];
            System.arraycopy(tokens, 0, ts, 0, tokens.length);
            ts[tokens.length] = sub;

            total.addAll(restore(ts, rest.substring(i)));
        }

        return total;
    }
}

Single Number II

【题目】Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

【解答】下面这种方法，是利用一个掩码来统计某一位的出现次数，这是一种比较常用的办法，具体的分析，我写过一篇文章。

public class Solution {
    public int singleNumber(int[] A) {
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            int count = 0, mask = 1<<i;
            for (int j = 0; j < A.length; j++)
                if ( (A[j] & mask) > 0 || (A[j] & mask) < 0 )
                    count++;

            // for the most integers the count should be 0 or 3
            if (count%3 > 0)
                ret |= mask;
        }
        return ret;
    }
}

Reverse Linked List II

【题目】Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

【解答】要做到 “in-place” 和 “one-pass”，大致思路是这样，[m,n] 段，先反转节点之间链接指向，然后再把 n 接到它本来前面的 [1,m) 段去，而把 m 接到它本来后面的 (n,null] 段去。

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode fake = new ListNode(0);
        fake.next = head;

        // get the mth node
        ListNode mth = fake;
        for (int i = 1; i < m; i++) {
            mth = mth.next;
        }

        ListNode cur = mth.next;
        ListNode tail = cur;
        int count = 1;

        ListNode prev = null;
        ListNode next = null;
        while (count <= n-m+1) {
            // shift link direction
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;

            count++;
        }

        // head/tail
        mth.next = prev;
        tail.next = next;

        return fake.next;
    }
}

Single Number

【题目】Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

【解答】用异或就好了，一个数异或它自己就为 0。

public class Solution {
    public int singleNumber(int[] A) {
        if(null==A)
            throw new IllegalArgumentException();
        int total = 0;
        for (int a : A)
            total ^= a;
        return total;
    }
}

Reverse Words in a String

【题目】

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

【解答】两个指针，一个指针 cur 只顾着从右往左走，另一个指针 wordEnd 始终占据单词后面的那个空格，这样每次 cur 发现空格的时候 substring(cur+1, wordEnd) 就是该单词。需要注意的是，题目说得很明确，需要注意 leading 和 trailing 的空格要去掉，还有中间连续的空格需要变成一个，所以需要有判断条件 wordEnd-1>cur，保证连续空格的情况下不会被写到字符串里面去，只有真正的单词出现的时候才需要 append 空格。

public class Solution {
    public String reverseWords(String s) {
        int wordEnd = s.length();
        int cur = wordEnd - 1;

        StringBuilder sb = new StringBuilder();

        while (cur>=0) {
            if (s.charAt(cur)==' ') {
                if (wordEnd-1>cur) {
                    if (sb.length()>0)
                        sb.append(' ');
                    sb.append(s.substring(cur+1, wordEnd));
                }
                wordEnd = cur;
            }

            cur--;
        }

        if (wordEnd-1>cur) {
            if (sb.length()>0)
                sb.append(' ');
            sb.append(s.substring(0, wordEnd));
        }

        return sb.toString();
    }
}

Simplify Path

【题目】Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

【解答】这个题目主要是考虑 case 是不是考虑完备，包括：

• ///
• /..
• a/
• ./a
• /…

public class Solution {
    public String simplifyPath(String path) {
        String[] tokens = path.split("/");
        String[] parsed = new String[tokens.length];

        int pos = 0;
        for (String token : tokens) {
            if ("".equals(token) || ".".equals(token)) {
                continue;
            } else if ("..".equals(token)) {
                if (pos>0) {
                    pos--;
                }
            } else {
                parsed[pos] = token;
                pos++;
            }
        }

        String init = "";
        if (path.startsWith("/"))
            init = "/";

        StringBuilder sb = new StringBuilder(init);
        boolean first = true;
        for (int i=0; i<pos; i++) {
            if (!first)
                sb.append('/');
            first = false;

            sb.append(parsed[i]);
        }

        return sb.toString();
    }
}

Rotate Image

【题目】You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

【解答】先在草稿纸上画画，就能发现下面代码中注释里面写的那个点的移动规律。也就是说，每次 rotate，都需要四个一组来进行操作。两个嵌套的 for 循环保证了主动发起 rotate 的单元是正方形的中心和两个相邻顶点的连线以及这两个顶点连线所构成的三角形（下图中的三个红圈是这个三角形的三个顶点）。

public class Solution {
    /**
     * (i,j) => (j,n-i)
     * (j,n-i) => (n-i,n-j)
     * (n-i,n-j) => (n-j,i)
     * (n-j,i) => (i,j)
     **/
    public void rotate(int[][] matrix) {
        int n = matrix.length-1;

        for (int i=0; i<=n; i++) {
            for (int j=i+1; j<=n-i; j++) {
                int n1 = matrix[i][j];
                int n2 = matrix[j][n-i];
                int n3 = matrix[n-i][n-j];
                int n4 = matrix[n-j][i];

                matrix[i][j] = n4;
                matrix[j][n-i] = n1;
                matrix[n-i][n-j] = n2;
                matrix[n-j][i] = n3;
            }
        }
    }
}

Rotate List

【题目】Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

【解答】用一个栈存放所有节点，然后出栈 k 个元素，把出栈的这 k 个元素放到原 head 的前面去。注意的是这么两个地方：

• rotate 的次数可能大于这个 list 元素的个数，因此需要取余；
• head 为空或者栈为空时的处理。

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (null==head)
            return head;

        Stack<ListNode> stack = new Stack<>();
        ListNode node = head;
        while(node!=null) {
            stack.push(node);
            node = node.next;
        }

        n = n % stack.size();
        if (n==0)
            return head;

        ListNode tail = stack.peek();
        for (int i=n; i>0; i--)
            node = stack.pop();

        stack.peek().next = null;
        tail.next = head;

        return node;
    }
}

Binary Tree Inorder Traversal

【题目】Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

【解答】递归的方式不用说了。非递归的方式，可以参考先序遍历那道题的思路，但是如果按照那个思路来做，在如下情形下是有问题的：

因为某节点 A 有左孩子，中序遍历要求先遍历左子树，因此要把 A 入栈，这没错；但是当把 A 出栈以后，A 节点因为有左孩子，又要入栈， 这就无限循环下去了。

因此稍微改进一下，凡是从栈中取出的节点，立即访问，并且在访问完毕以后，绝不要放回栈里面，并且让节点指针指向它的右孩子，这样就可以保证访问过的节点不可能再被访问到：

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (null!=node || !stack.isEmpty()) {
            if (null!=node) {
                stack.push(node);
                node = node.left;
            } else {
                // node is null, but stack is not empty
                node = stack.pop();
                if (null==node)
                    return list;
                list.add(node.val);

                node = node.right;
            }
        }

        return list;
    }
}

Set Matrix Zeroes

【题目】Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

【解答】先遍历一遍，把需要置为 0 的行和列都保存下来，再置零。

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length==0 || matrix[0].length==0)
            return;
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();

        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (matrix[i][j]==0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }

        for (int row : rows) {
            for (int j=0; j<matrix[0].length; j++) {
                matrix[row][j] = 0;
            }
        }

        for (int col : cols) {
            for (int i=0; i<matrix.length; i++) {
                matrix[i][col] = 0;
            }
        }
    }
}

题是做出来了，但是这个办法的空间复杂度是 O(m+n)，按照题中的 follow up，应该是还可以继续优化的。比如用位存储是一个节约空间的好办法。当然，我也考虑过看看能不能用常量的空间复杂度，我当时的做法是在第一遍遍历的时候就给需要置为 0 的行列元素全部标记为一个特殊值，但是对于一个 int 型的数组，没有一个特殊值可以供我标记。于是我去网上找了别人的解法，发现确实是有办法做到这一点的，其中一个办法就是，先把整个矩阵的第 1 行和第 1 列拿来作置零标尺。比如第 k 行必须置零，那么就把 matrix[k-1][0] 置为 0，到最后在根据标尺上的信息来完成全部的置零操作。

Search a 2D Matrix

【题目】Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.【解答】大致思路是，先二分查找找到在哪一行，再二分查找找到在该行上的哪一列。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (null==matrix || matrix.length==0 || matrix[0].length==0)
            return false;
        
        int r = matrix.length-1;
        int c = matrix[0].length-1;
        
        // find the row
        int min = 0;
        int max = r;
        int row = -1;
        while (min<=max) {
            int mid = (max+min)/2;
            if (target==matrix[mid][0] || target==matrix[mid])
                return true;
            
            if (target<matrix[mid][0]) {
                max = mid-1;
                continue;
            } else if (target>matrix[mid]) {
                min = mid+1;
                continue;
            } else {
                row = mid;
                break;
            }
        }
        
        if (row==-1)
            return false;
        
        // seek for the element
        min = 1;
        max = c-1;
        while (min<=max) {
            int mid = (min+max)/2;
            if (matrix[row][mid]==target)
                return true;
            else if (matrix[row][mid]>target)
                max = mid-1;
            else
                min = mid+1;
        }
        
        return false;
    }
}

Search for a Range

【题目】Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

【解答】核心思想还是二分查找，变化的地方在于，在每次循环中，如果找到了，这个时候需要对 [min,mid-1] 和 [mid+1,max] 这两段继续使用二分查找分别去寻找每段的分界线 l 和 r，使得这两条分界线组成的 range [l,r] 为所求。

public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (null==A || A.length==0)
            return new int[]{-1,-1};

        int min = 0;
        int max = A.length-1;

        while (min<=max) {
            int mid = (max+min)/2;
            if (A[mid]<target) {
                min = mid+1;
                continue;
            } else if (A[mid]>target) {
                max = mid-1;
                continue;
            }

            // A[mid]==target, search for the range in [min,max]
            int l=mid;
            int r=mid;

            int lmax = mid-1;
            int rmin = mid+1;

            while (min<=lmax) {
                int m = (min+lmax)/2;
                if (A[m]<target) {
                    min = m+1;
                    continue;
                } else {
                    lmax = m-1;
                    l = m;
                    continue;
                }
            }

            while (max>=rmin) {
                int m = (max+rmin)/2;
                if (A[m]>target) {
                    max = m-1;
                    continue;
                } else {
                    rmin = m+1;
                    r = m;
                    continue;
                }
            }

            return new int[]{l,r};
        }

        return new int[]{-1,-1};
    }
}

Search Insert Position

【题目】Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

【解答】基于二分搜索，稍微改一下实现。如果找到了，皆大欢喜；如果没找到，要让指针最后处于 left>right 的状态，这样 left 就是要插入的位置。

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length==0)
            return 0;

        int left=0, right=nums.length-1;
        while(left<=right) {
            int mid = (left+right)/2;
            if (nums[mid]==target)
                return mid;
            else if (nums[mid]>target)
                right = mid-1;
            else
                left = mid+1;
        }

        // left>right
        return left;
    }
}

Search in Rotated Sorted Array II

【题目】Follow up for “Search in Rotated Sorted Array”:

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

【解答】相较于 “Search In Rotated Sorted Array”（那道题是 Hard 难度的，这道题是 Medium 的），就多了下面 16 行的那个分支，在发现 A[end] 和 A[start] 相等的时候，我就不知道哪一侧才有最大最小值的分界点了。这个最糟糕情况下的复杂度就不再是 log n 了，而是 n。

public class Solution {
    public boolean search(int[] A, int target) {
        return search(A, target, 0, A.length-1);
    }

    private boolean search(int[] A, int target, int start, int end) {
        if (start>end)
            return false;

        int mid = (end+start)/2;

        if (target==A[mid])
            return true;

        // in this case i don't know which part is increasing
        if (A[end]==A[mid]) {
            return search(A, target, start, mid-1) || search(A, target, mid+1, end-1);
        }

        if (A[end]>A[mid]) { // the right part is increasing
            if (target>A[end] || target<A[mid]) {
                return search(A, target, start, mid-1);
            } else {
                return search(A, target, mid+1, end);
            }
        } else { // the left part is increasing
            if (target<A[start] || target>A[mid]) {
                return search(A, target, mid+1, end);
            } else {
                return search(A, target, start, mid-1);
            }
        }
    }
}

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》