Happy Coding: April 2015

Thursday, April 30, 2015

[LeetCode] Pow(x, n)

Pow(x, n)

Implement pow(x, n).
Solution: Bit Manipulation. The idea is that we look at the i-th bit of n, if it is 1, we multiple by x^{2^i}.
Pay attention to the case where n is negative.

public class Solution {
    public double myPow(double x, int n) {
        boolean neg = false;
        if (n < 0) {
            n = -1 * n;
            neg = true;
        }
        double result = 1.0;
        double mul = x;
        int mask = 1;
        while (n > 0) {
            if ((n & mask) > 0) {
                result *= mul;
            }
            mul = mul * mul;
            n = n >> 1;
        }
        if (neg) {
            return 1.0 / result;
        }
        return result;
    }
}

Wednesday, April 29, 2015

[LeetCode] Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: Binary Search!
Suppose a = (int)sqrt(x), then a^2 <= x < (a+1)^2.
Pay attention to overflow.

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int low = 1;
        int high = x;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (x / mid >= mid && x / (mid + 1) < mid + 1) {
                return mid;
            }
            if (x / mid < mid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return 0;
    }
}

Tuesday, April 28, 2015

[LeetCode] Isomorphic Strings

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Solution: Hash table. The test cases assume ASCII characters. A valid mapping is indeed a bijection. The easiest way to determine whether such a mapping exists is to test both directions. The beauty of symmetry!

public class Solution {
    public boolean isIsomorphicOneWay(String s, String t) {
        char[] map = new char[256];
        Arrays.fill(map, '*');
        for (int i = 0; i < s.length(); i++) {
            int idx = (int)s.charAt(i);
            if (map[idx] == '*') {
                map[idx] = t.charAt(i);
            } else {
                if (map[idx] != t.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        return isIsomorphicOneWay(s, t) &&
               isIsomorphicOneWay(t, s);
    }
}

[LeetCode] Candy

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Solution: For each child, we look at the least number of candies he/she should get from left to right, then from right to left, denoted by L and R, respectively. Then the least number of candies he/she should get in the end is max(L, R).
Correctness: It can be seen from the following four cases.
1. For any child with local minimum rating, we can safely assign ONE candy.
2. For any child with local maximum rating, we look at the left closest child with local minimum rating, and the right closest child with local minimum rating.
3. For any child with increasing rating, we look at the left closest child with local minimum rating.
4. For any child with decreasing rating, we look at the right closest child with local minimum rating.
Note: In the following Java code, we can use one additional array instead of two. In that case, when we scan from right to left, we update the same array. Furthermore, one may be able to do this in place (i.e., without an additional array). That can be done by each time finding two consecutive local minimums with candy number ONE, and compute the number of candies in between (based on the correctness analysis).

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 0) {
            return 0;
        }
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) {
                left[i] = left[i-1] + 1;
            } else {
                left[i] = 1;
            }
        }
        right[n-1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                right[i] = right[i+1] + 1;
            } else {
                right[i] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }
        return sum;
    }
}

[LeetCode] Validate Binary Search Tree

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Solution 1: For each sub-tree, we maintain its lower bound and upper bound. The tricky part is to deal with the maximum integer and the minimum integer. In the following Java code, I used two additional flags to denote whether the lower bound is -infty and whether the upper bound is +infty, respectively.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(
        TreeNode root, 
        int lower_bound, 
        int upper_bound, 
        boolean neg_infty, 
        boolean pos_infty
    ) {
        if (root == null) return true;
        if (root.val <= lower_bound && !neg_infty) return false;
        if (root.val >= upper_bound && !pos_infty) return false;
        return isValidBST(root.left, lower_bound, root.val, neg_infty, false) &&
               isValidBST(root.right, root.val, upper_bound, false, pos_infty);
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE, true, true);
    }
}

Solution 2: In-order traversal. The resulting list should be in the increasing order. Simple, yet it uses additional space.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        ArrayList<Integer> list = inorderTraversal(root);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i-1) >= list.get(i)) {
                return false;
            }
        }
        return true;
    }
}

Monday, April 27, 2015

[LeetCode] Reorder 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}.

Solution: First we count the total number of elements in the linked list, and we reverse the second half. In the end, we merge these two lists.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode h = reverseList(head.next);
        head.next = null;
        ListNode p = h;
        while (p.next != null) {
            p = p.next;
        }
        p.next = head;
        return h;
    }
    
    public void reorderList(ListNode head) {
        int num = 0;
        ListNode p = head;
        while (p != null) {
            num++;
            p = p.next;
        }
        if (num <= 2) return;
        int mid = (num + 1) / 2;
        p = head;
        while (mid > 1) {
            mid--;
            p = p.next;
        }
        ListNode h = reverseList(p.next);
        p.next = null;
        p = head;
        ListNode q = h;
        while (p != null && q != null) {
            ListNode r = q.next;
            q.next = p.next;
            p.next = q;
            p = q.next;
            q = r;
        }
        return;
    }
}

[LeetCode] Count Primes

Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n

Solution: Hash table + Sieve of Eratosthenes

public class Solution {
    public int countPrimes(int n) {
        if (n < 2) return 0;
        int[] arr = new int[n];
        Arrays.fill(arr, 0);
        for (int i = 2; i < n; i++) {
            if (arr[i] == 1) { 
                continue;
            }
            for (int j = 2*i; j < n; j += i) {
                arr[j] = 1;
            }
        }
        int sum = 0;
        for (int i = 2; i < n; i++) {
            sum += (1 - arr[i]);
        }
        return sum;
    }
}

A slightly optimized version:

public class Solution {
    public int countPrimes(int n) {
        if (n < 2) return 0;
        int[] arr = new int[n];
        Arrays.fill(arr, 0);
        for (int i = 2; i <= Math.sqrt(n-1); i++) {
            if (arr[i] == 1) { 
                continue;
            }
            for (int j = i*i; j < n; j += i) {
                arr[j] = 1;
            }
        }
        int sum = 0;
        for (int i = 2; i < n; i++) {
            sum += (1 - arr[i]);
        }
        return sum;
    }
}

Sunday, April 26, 2015

[LeetCode] Insertion Sort List

Insertion Sort List
Sort a linked list using insertion sort.
Solution: The power of recursion. We first sort the remaining list, and then we insert the head node.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode h = insertionSortList(head.next);
        head.next = null;
        if (head.val < h.val) {
            head.next = h;
            return head;
        }
        ListNode pre = h;
        ListNode cur = h.next;
        while (cur != null && cur.val < head.val) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = head;
        head.next = cur;
        return h;
    }
}

Friday, April 24, 2015

[LeetCode] Largest Number

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

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

Solution: Sorting! We need to implement the compare() function. A nice comparison can be done using strings, instead of integers. If we use integers, it would overflow. Special attention is also needed when we have at least two 0's in the array.
The following Java code has both selection sort and merge sort, while it only calls merge sort.

public class Solution {
    public boolean compare(int a, int b) {
        return compare("" + a + b, "" + b + a);
    }
    
    public boolean compare(String s, String t) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < t.charAt(i)) {
                return false;
            } 
            if (s.charAt(i) > t.charAt(i)) {
                return true;
            }
        }
        return true;
    }
    
    public void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int idx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (compare(nums[j], max)) {
                    max = nums[j];
                    idx = j;
                }
            }
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
        }
    }
    
    public int[] mergeSort(int[] nums) {
        if (nums.length < 2) { 
            return nums;
        }
        
        int mid = (nums.length - 1) / 2;
        int[] left = mergeSort(
            Arrays.copyOfRange(nums, 0, mid + 1)
        );
        int[] right = mergeSort(
            Arrays.copyOfRange(nums, mid + 1, nums.length)
        );
        
        int i = 0;
        int j = 0;
        int k = 0;
        int[] arr = new int[nums.length];

        while (i < left.length && j < right.length) {
            if (compare(left[i], right[j])) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        
        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
        
        return arr;
    }
    
    public String largestNumber(int[] nums) {
        nums = mergeSort(nums);
        String str = "";
        for (int num : nums) {
            str = str + num;
        }
        if (str.charAt(0) == '0') { 
            return "0";
        }
        return str;
    }
}

Thursday, April 23, 2015

[LeetCode] Repeated DNA Sequences

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution: We use HashMap, but if we directly use strings of length 10 as keys, LeetCode OJ will throw the error "Memory Limit Exceeded". The main trick is to store an integer representation of a string of length 10. Since we only have 'A', 'C', 'G', 'T', we can use 2 bits to represent each of them, and a string of length 10 can be represented using 20 bits, within 32 bits. We use bit operation | to calculate such an integer representation.
Alternatively, one may also use a hash table instead of a hash map. An array of size 2^20 is sufficient, since a string of length 10 can be represented using 20 bits.

public class Solution {
    public int mapStringToInt(String str) {
        int result = 0;
        for (int i = 0; i < str.length(); i++) {
            switch (str.charAt(i)) {
                case 'A': result |= 0; break;
                case 'C': result |= 1; break;
                case 'G': result |= 2; break;
                case 'T': result |= 3; break;
                default: 
            }
            result <<= 2;
        }
        return result;
    }
    
    public List<String> findRepeatedDnaSequences(String s) {
        ArrayList<String> list = new ArrayList<String>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < s.length() - 9; i++) {
            String str = s.substring(i, i + 10);
            int val = mapStringToInt(str);
            if (map.containsKey(val)) {
                if (map.get(val) == 1) {
                    list.add(str);
                    map.put(val, 0);
                }
            } else {
                map.put(val, 1);
            }
        }
        return list;
    }
}