Happy Coding

Sunday, May 3, 2015

[LeetCode] 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],
]

Solution: Note that combine(n, k) is the union of the following two, depending on whether n is used:
1. combine(n - 1, k).
2. combine(n - 1, k - 1), plus the element n.

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        if (n < k || k == 0) {
            return list;
        }
        if (k == 1) {
            for (int i = 1; i <= n; i++) {
                ArrayList<Integer> l = new ArrayList<Integer>();
                l.add(i);
                list.add(l);
            }
            return list;
        }
        list.addAll(combine(n - 1, k));
        List<List<Integer>> li = combine(n - 1, k - 1);
        for (List<Integer> ll : li) {
            ArrayList<Integer> l = new ArrayList<Integer>(ll);
            l.add(n);
            list.add(l);
        }
        return list;
    }
}

[LeetCode] Populating Next Right Pointers in Each Node

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,

After calling your function, the tree should look like:

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

Solution: Breath-first Search! The beauty lies in that the pointers TreeLinkNode *next in the previous level help scan the current level!

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode p = root;
        while (p != null) {
            TreeLinkNode q = p;
            while (q != null) {
                if (q.left != null) {
                    q.left.next = q.right;
                }
                if (q.right != null) {
                    if (q.next != null) {
                        q.right.next = q.next.left;                        
                    } else {
                        q.right.next = null;
                    }
                }
                q = q.next;
            }
            p = p.left;
        }
        return;
    }
}

[LeetCode] Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Solution: The observation is that the desired linked list is a concatenation of root, flatten(root.left), and flatten(root.right).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        if (root.left == null) {
            return;
        }
        flatten(root.left);
        TreeNode p = root.left;
        while (p.right != null) {
            p = p.right;
        }
        p.right = root.right;
        root.right = root.left;
        root.left = null;
        return;
    }
}

Saturday, May 2, 2015

[LeetCode] Fraction to Recurring Decimal

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

Solution: The integer part is trivial, and for the decimal part, we simulate the division procedure. A hash map is used to detect whether it is repeating. The tricky part is to deal with overflow/underflow. For example, see line 5 - 9, and line 24. The following Java code did not aim to take care of all the corner cases, and it only aimed to pass the LeetCode OJ, i.e., the test cases provided by the LeetCode OJ platform.
Alternatively, one may use type long to resolve possible overflow/underflow issues. See, e.g. this post.

public class Solution {
 public String fractionToDecimal(int numerator, int denominator) {
        int n = numerator;
        int d = denominator;
        if (n == Integer.MIN_VALUE) {
            String s = n + "";
            if (d == 1) return s;
            if (d == -1) return s.substring(1);
        }
        if (1.0 * n / d < 0) {
            return "-" + fractionToDecimal(-n, d);
        }
        int int_part = n / d;
        StringBuffer sb = new StringBuffer();
        sb.append(int_part);
        n = n - d * int_part;
        if (n == 0) {
            return sb.toString();
        }
        sb.append('.');
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int idx = sb.toString().length() - 1;
        while (n != 0) {
            int digit = (int) (1.0 * n / d * 10);
            sb.append(digit);
            idx++;
            map.put(n, idx);
            n = 10 * n - d * digit;
            if (map.containsKey(n)) {
                sb.append(')');
                sb.insert((int)map.get(n), '(');
                return sb.toString();
            }
        }
        return sb.toString();
 }
}

Friday, May 1, 2015

[LeetCode] Subsets

Subsets

Given a set of distinct integers, nums, 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 nums = [1,2,3], a solution is:

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

Solution: The beauty of recursion!

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        if (nums.length == 0) {
            ArrayList<Integer> l = new ArrayList<Integer>();
            list.add(l);
            return list;
        }
        Arrays.sort(nums);
        List<List<Integer>> li = subsets(
                Arrays.copyOfRange(nums, 0, nums.length - 1)
            );
        list.addAll(li);
        for (List<Integer> ll : li) {
            ArrayList<Integer> l = new ArrayList<Integer>(ll);
            l.add(nums[nums.length - 1]);
            list.add(l);
        }
        return list;
    }
}

[LeetCode] Permutations

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].

Solution: The beauty of recursion!

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        if (nums.length == 0) {
            return list;
        }
        if (nums.length == 1) {
            ArrayList<Integer> l = new ArrayList<Integer>();
            l.add(nums[0]);
            list.add(l);
            return list;
        }
        List<List<Integer>> li = permute(
                Arrays.copyOfRange(nums, 1, nums.length)
            );
        for (List<Integer> ll : li) {
            for (int i = 0; i <= ll.size(); i++) {
                ArrayList<Integer> l = new ArrayList<Integer>(ll);
                l.add(i, nums[0]);
                list.add(l);
            }
        }
        return list;
    }
}

[LeetCode] Permutation Sequence

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):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

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

Solution: From left to right, we compute each digit in the desired sequence.
Some simple observations:
1. If k denotes the last sequence, construct the last sequence and return;
2. Compute the highest digit, and update k.

public class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * (i + 1);
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        StringBuffer sb = new StringBuffer();
        int m = n - 1;
        while (k > 0) {
            if (k == factorial[m]) {
                for (int i = list.size() - 1; i >= 0; i--) {
                    sb.append(list.get(i));
                }
                return sb.toString();
            } else {
                int t = (k - 1) / factorial[m - 1];
                sb.append(list.remove(t));
                k = k - t * factorial[m - 1];
                m--;
            }
        }
        return sb.toString();
    }
}