Monthly Archives: January 2016

Find LCA in Binary Tree, Find LCA in BST

I wrote finding lca long time ago. Today, I learned this more concise code for finding LCA in Binary Tree.

The idea is that if there is no p or q in bottom, return null. Or return p, q or root.

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == p || root == q || root == null) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if (left != null) {
        return left;
    }
    return right;
}

Check my code on github: link

 

Below is the finding LCA in BST.

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    if (root.val >= min && root.val <= max) {
        return root;
    }
    return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}

Check my code on github: link

Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, – and *.

Example 1
Input: “2-1-1”.

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: “2*3-4*5”

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

Solution. For String input, go through each char. If a char is ‘+’, ‘-‘ or ‘*’, then we calculate left and right. Left and right will be both List. Calculate all element combination in both left and right, and put in result.

Check my code on github: link

Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

Solution. The idea is that suppose by adding some elements, we can get the sum s. And if there is an element e less than s that we haven’t used. Then we can get reach [1,…, s+e].

For example, 1, 2, 3, 4, 8. By summing 1+2+3+4, we know it can reach [1,…,10]:
[1], [2], [3], [4], [1 + 4], [2 + 4], [3 + 4], [1 + 3 + 4], [1 + 2 + 3 + 4]

The next one is 8 which is less than sum 10. Then by adding 10 + 8 = 18, we know that it can get reach [1,…,18].

Let’s go back to the problem. Take [1, 4, 10], n = 20 for example. It can reach 1 by [1]. And it can’t reach 2. So we put 2 in array.

1 + 2 = 3. We know it can reach 3. Now 3 is the furthest it can reach.

Next element is 4, so we can reach 4. 3 + 4 = 7, we know by now, it can reach 7.

Then next element is 10. 7 can’t reach it. So we put 8 after 7, 7 + 8 = 15. We know it can reach 15.

By now, we can’t reach 20 yet. So we put 16, we have 16 + 15 = 31.

By total, we put 3 numbers.

Explanation is a bit complex. Original solution is from here.

Check my code on github: link

WordDistanceI, II, III

3 problems are from leetcode.

WordDistanceI

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Solution. This is a easy one. We maintain an index for the position where the last word is. We just go through words[] one time and update min and index.

Check my code on github: link

 

WordDistanceII

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

Solution. Popular solution is to use HashMap and ArrayList. For each word, it maintains a list. Put the index where this word happened in list. In this way, the list has ascending order. When we compare 2 words distance, we try to find the min value between 2 lists. This is discussed in this post. This solution takes O(n) time for building structure, O(n) time for searching min distance.

Another idea is that we put all combination of 2 words in the HashMap, in this way, we can get the result in O(1) time. This solution takes O(n^2) time for building the structure.

Check my code on github: link

 

WordDistanceIII

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.

Solution. This one can be easily derived from WordDistanceI. We change to calculate distance when 2 words are equal.

Because I didn’t purchase leetcode, I’m not sure if this question is also applied to WordDistanceII. If it is, the change is not hard neither.

Check my code on github: link

Strobogrammatic Number II, III

Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,

Given n = 2, return [“11″,”69″,”88″,”96”].

Solution. The basic idea is to iterate from inside to outside. If n is even, we just start from “”. If n is odd, the initial inside should start from”0″, “1”, “8”.
When it reach the outside(length is n), we should ignore those whose first element is “0”.

In leetcode discussion, most popular way is similar to below:

public static final char[][] chs = {{'6', '9'}, {'9', '6'}, {'1', '1'}, {'8', '8'}, {'0', '0'}};

public static List<String> findStrobogrammatic(int n) {
    return findHelper(n, n);
}

public static ArrayList<String> findHelper(int num, int n) {
    if (num == 1) {
        return new ArrayList<String>(Arrays.asList("0", "1", "8"));  // handle the middle one
    }
    else if (num <= 0) {
        return new ArrayList<String>(Arrays.asList(""));  // handle the middle one
    }
    List<String> list = findHelper(num - 2, n);
    int to = (num == n ? 3 : 4);    // if is last outside, 0 shouldn't be considered
    ArrayList<String> newList = new ArrayList<String>();
    for (String str : list) {
        for (int i = 0; i <= to; i++)
            newList.add(chs[i][0] + str + chs[i][1]);
    }
    list = null;
    return newList;
}

It is a very awesome way of concise code. But to me, first it is not easy to think this method. Second, it is not a common way.

However, I feel more comfortable with code like below. It is more standard. It is a bit longer. But I can finish it within 10 minutes. You can find my other recursion solution all coming up like this structure.

public static final char[][] chs = {{'6', '9'}, {'9', '6'}, {'1', '1'}, {'8', '8'}, {'0', '0'}};

public static List<String> findStrobogrammatic(int n) {
    List<String> ans = new ArrayList<String>();
    if ((n & 1) == 1) {
        findHelper(ans, new StringBuffer("1"), 1, n);
        findHelper(ans, new StringBuffer("0"), 1, n);
        findHelper(ans, new StringBuffer("8"), 1, n);
    }
    else {
        findHelper(ans, new StringBuffer(), 0, n);
    }
    return ans;
}

public static void findHelper(List<String> ans, StringBuffer buf, int pos, int n) {
    if (buf.length() >= n && buf.charAt(0) != '0') {
        ans.add(buf.toString());
        return;
    }
    for (int i = 0; i < 4; i++) {
        buf.insert(0, chs[i][0]);
        buf.append(chs[i][1]);
        findHelper(ans, buf, pos + 2, n);
        buf.deleteCharAt(0);
        buf.deleteCharAt(buf.length() - 1);
    }
}

Naturally, I come up with solution to Strobogrammatic Number III: Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high. For example, Given low = “50”, high = “100”, return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Solution. For this problem, key is to compare the buf and lo, buf and high by below function. If buf is between lo and high, then ans++.

public static int compare(String str1, String str2) {
    if (str1.length() != str2.length())
        return str1.length() - str2.length();
    int n = str1.length();
    for (int i = 0; i < n; i++) {
        if (str1.charAt(i) != str2.charAt(i)) {
            return str1.charAt(i) - str2.charAt(i);
        }
    }
    return 0;
}

Check my code on github: StrobogrammaticII(solution1), StrobogrammaticII(solution2), StrobogrammaticIII

Object.hashCode()

I tried below code:

int[] a1 = {1, 2};
int[] a2 = {1, 2};
System.out.println(a1.hashCode());
System.out.println(a2.hashCode());
System.out.println(Arrays.hashCode(a1));
System.out.println(Arrays.hashCode(a2));

The result is:

1356652206
1419746043
994
994

The reason is because hashCode() int[] is not overwritten. It is treated as an object. Read below explanation from javaworld, we know hashCode() for Object is a mapping to memory.

Basically the default implementation of hashCode() provided by Object is derived by mapping the memory address to an integer value. If look into the source of Object class , you will find the following code for the hashCode.

Factor Combination

leetcode 254. Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.

Note:
Each combination’s factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
You may assume that n is always positive.
Factors should be greater than 1 and less than n.

Examples:
input: 1
output:
[]

input: 37
output:
[]

input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]

input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]

Solution. Each time, put a factor in list. But the factor we put should be equal to or greater than the last one we put in. The end condition is when n is 1.

Check my code on github: link

Digital Root

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Solution. We need to refer to this wiki digital root. Basically, the result is num mod 9. But we need to exclude 2 exceptions:
1. When num is 0, we need to return 0.
2. When mod is 0, we need to return 0.

In this way, easiest one should be 

check my code on github: link

3 Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up: Could you solve it in O(n2) runtime?

Solution. This problem is similar to Number of Triangle. Let’s see we have i, j fixed. As long as nums[i] + nums[j] + nums[k] < target, then all set of (i, j, j + 1), (i, j, j + 2),…, (i, j, k – 1), (i, j, k) are qualified.

By this characteristic, We use i for outer loop from 0 to n – 1. For each loop, we set a left =  n + 1, right = n – 1. When sum less than target, we accumulate result and left++. Or we do right–.

Check my code on github: link

Single Number III

leetcode[Single Number III].

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Solution. Since there are only 2 numbers which appears 1 time, other number appears 2 times. Let assume the number which appears 1 time are a and b. When we do xor operation on each element in nums[], we get result of xorNum = a xor b.

Now, let’s get the first 1 in the xorNum counting fro right. We can do xorNum & (-xorNum). This skill is used in Indexed Binary Tree.

Let’s loop each num in nums[] for another round. We can divide num in 2 groups. One group has num & xorNum == 0, another group has num & xorNum != 0. In this way, we can get the 2 results.

check my code on github: link