Posted on   |  

Question

[LeetCode 112] Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Submission

Java Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return (root.val == sum);
        } else {
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }
    }
}

Posted on   |  

Question

[LeetCode 300] Given an unsorted array of integers, find the length of longest increasing subsequence.

Submission

Similar to [LeetCode 334], solve the question by using dynamic programming, and the algorithm run in $O(n^2)$ time and can be speed up to $O(nlogn)$ by using binary search.

Solve with dynamic programming

The easiest solution which take $O(n^2)$ running time

Java Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] length = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            length[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < length.length; i++) {
            if (length[i] > maxLength) {
                maxLength = length[i];
            }
        }
        return maxLength;
    }
}

By using binary search the running time can be reduced to $O(nlogn)$

Java Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int maxLength = 0;
        int[] lastIndex = new int[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            int lo = 1;
            int hi = maxLength;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (nums[lastIndex[mid]] < nums[i]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            int newLength = lo;

            lastIndex[newLength] = i;

            if (newLength > maxLength) {
                maxLength = newLength;
            }
        }

        return maxLength;
    }
}

Explanation

Using an addition array lastIndex to store the index of the last elements of possible increasing subsequences in nums, lastIndex[j] representing the index of the smallest elements in nums in the subsequences with length = j. maxLength will be used to mark the maximum length of the increasing subsequence in the current iteration.

nums = {9, 8, 2, 5, 3, 7, 19, 11, 9} and i = 8

When maxLength = 5, this

ilastIndex[i]Representing Sequence
0--
122
242, 3
352, 3, 7
562, 3, 6

For each iteration, we would like to know whether nums[i] will generate a longer/better increasing subsequences. By using binary search, to find the maximum length l of a subsequences where its last number is just smaller than nums[i], and because the last value of the sequence represented by lastIndex[l+1] is less than the nums[i] (i.e nums[lastIndex[l+1]] > nums[i]), thus, it generate a better increasing subsequences with length = l+1, and lastIndex[l+1] will be updated. If l+1 is greater than the current maximun length, it indicates that a longer increasing subsequence can be found.

References

  1. Longest Increasing Subsequence https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Posted on   |  

Question

[LeetCode 334] Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Submission

Using dynamic programming, find if there exist increasing subsequence with length greater than or equal to 3

Java Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) return false;

        int[] length = new int[nums.length];

        for (int i = 0; i < length.length; i++) {
            length[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                }
                if (length[i] >= 3) {
                    return true;
                }
            }
        }

        return false;
    }
}

Posted on   |  

Question

[LeetCode 100] Given two binary trees, write a function to check if they are equal or not.

Submission

Java Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
    }
}

Posted on   |  

Question

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

Submission

Find the digital root of any positive number. The solution appear periodically from 1 to 9.

Java Submission
1
2
3
4
5
public class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
}

Reference

  1. Digital root https://en.wikipedia.org/wiki/Digital_root