Monthly Archives: August 2016

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution. Loop from end to start. In this way, we can do this in-place.

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int k = m + n - 1;
    m--;
    n--;
    while (m >= 0 && n >= 0) {
        if (nums1[m] > nums2[n]) {
            nums1[k--] = nums1[m--];
        }
        else {
            nums1[k--] = nums2[n--];
        }
    }
    while (m >= 0) {
        nums1[k--] = nums1[m--];
    }
    while (n >= 0) {
        nums1[k--] = nums2[n--];
    }
}

Check my code on github.

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

Solution. Let’s first talk about the normal Subset problem, which doesn’t has duplicate. There is a loop way rather than recursion. Let’s say [1, 2, 3]. Assume we already have subset(1, 2), which is {[], [1], [2], [1, 2]}.

For 3, we can either add it {[], [1], [2], [1, 2]}

or not add it {[3], [1, 3], [2, 3], [1, 2, 3]}.

So we will have subset(1, 2, 3), which is {[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]}. It’s like for each element, we can either pick up or not pick up it.

For Subsets II problem, let’s say we want to get subset for [1, 2, 3, 3]. Assume we have subset(1, 2) = {[], [1], [2], [1, 2]}. Based on subset(1, 2), we can either add zero 3, add one 3, or two 3 in the subset(1, 2). So the process is like:

public static List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>(Collections.singleton(new ArrayList<>()));
    Arrays.sort(nums);
    int i = 0;
    while (i < nums.length) {
        int next = i + 1;
        while (next < nums.length && nums[next] == nums[i]) {
            next++;
        }
        int size = ans.size();
        for (int j = 0; j < size; j++) {
            List<Integer> curr = new ArrayList<>(ans.get(j));
            for (int k = 1; k <= next - i; k++) {
                curr.add(nums[i]);
                ans.add(new ArrayList<>(curr));
            }
        }
        i = next;
    }
    return ans;
}

Check my code on github.

leetcode 91.

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution. This is another dp problem. If we want to compute str[X1, X2, …, Xi-2, Xi-1, Xi].

1. Check if Xi is a valid one letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2, Xi-1]

2. Check if Xi-1Xi is a valid two letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2]

public static int numDecodings(String s) {
    if (s.length() == 0 || s.charAt(0) == '0') {
        return 0;
    }
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 1; i < s.length(); i++) {
        int oneLetterNum = Integer.parseInt(s.substring(i, i + 1));
        if (oneLetterNum > 0) {
            dp[i + 1] += dp[i];
        }
        int twoLetterNum = Integer.parseInt(s.substring(i - 1, i + 1));
        if (twoLetterNum >= 10 && twoLetterNum <= 26) {
            dp[i + 1] += dp[i - 1];
        }
    }
    System.out.println(Arrays.toString(dp));
    return dp[s.length()];
}

Check my code on github.

leetcode 92.

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.

Solution. Should return head if head is null or head only has 1 element.

We use a dummyHead pointing to head. Then we put start to the m – 1 position, put pre to m position, put curr to m + 1 position. Each time, we move curr after start. At the beginning, start points to dummyHead.  Process for reversing [2..4] is like below.

If there are only 2 elements, the initial is like this:

public static ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode start = dummyHead;
    for (int i = 1; i < m; i++) {
        start = start.next;
    }
    ListNode pre = start.next, curr = start.next.next;
    for (int i = 1; i <= n - m; i++) {
        pre.next = curr.next;
        curr.next = start.next;
        start.next = curr;
        curr = pre.next;
    }
    return dummyHead.next;
}

Check my code on github.

leetcode 97.

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution. This is a good exercise for dp. The regularity is like below.

public static boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) {
        return false;
    }
    boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
    dp[0][0] = true;
    for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) != s3.charAt(i)) {
            break;
        }
        dp[i + 1][0] = true;
    }
    for (int j = 0; j < s2.length(); j++) {
        if (s2.charAt(j) != s3.charAt(j)) {
            break;
        }
        dp[0][j + 1] = true;
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            // should pay attention that it is i + j - 1, not i + j - 2
            dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
                    || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
        }
    }
    return dp[s1.length()][s2.length()];
}

Check my code on github.

leetcode 99.

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Solution. This problem is a difficult one. If we want to solve it in O(n) time and O(1) space, we need Morris Traversal. Besides, we need a decent code to find the swapped position in sorted array. Refer these two posts for detail: Morris Traversal, Recover Sorted Array

public static void recoverTree(TreeNode root) {
    TreeNode pre = null, curr = root, first = null, second = null;
    while (curr != null) {
        if (curr.left == null) {    // pop point and compare
            if (pre != null && curr.val < pre.val) {
                if (first == null) {
                    first = pre;
                }
                second = curr;
            }
            pre = curr;
            curr = curr.right;
            continue;
        }
        TreeNode rightMost = curr.left;
        while (rightMost.right != null && rightMost.right != curr) {
            rightMost = rightMost.right;
        }
        if (rightMost.right == null) {
            rightMost.right = curr;
            curr = curr.left;
        }
        else {
            if (pre != null && curr.val < pre.val) {
                if (first == null) {
                    first = pre;
                }
                second = curr;
            }
            pre = curr;
            curr = curr.right;
            rightMost.right = null;
        }
    }
    int val = first.val;
    first.val = second.val;
    second.val = val;
}

Check my code on github.

Given a sorted array. Two elements are swapped. Recover this array.

Solution. Think about the case1:

Original array = [1, 2, 3, 4, 5, 6, 7].

Swapped array = [1, 7, 3, 4, 5, 6, 2].

And we have first and second with Integer type. In this way, we know
If arr[i] > arr[i + 1] and first == null, we have first = i.
If arr[i] > arr[i + 1] and first != null, we have second = i + 1

Another exception case happens when the swapped element are together:

Original array = [1, 2, 3, 4, 5, 6, 7].

Swapped array = [1, 3, 2, 4, 5, 6, 7].

In this way,
If arr[i] > arr[i + 1] and first == null, we have first = i, second = i + 1

Considering above 2 cases, below is a concise code for it:

public static void recoverArray(int[] arr) {
    Integer first = null, second = null;
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            if (first == null) {
                first = i;
            }
            second = i + 1;
        }
    }
    int tmp = arr[first];
    arr[first] = arr[second];
    arr[second] = tmp;
}

Check my code on github.