Buttercola: September 2018

Wednesday, September 26, 2018

Leetcode 376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

Code (Java):

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        int[] dp = new int[nums.length];
        int[] mode = new int[nums.length];
         
        int maxLen = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && mode[j] < 1) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        mode[i] = 1;
                    }
                } else if (nums[i] < nums[j] && mode[j] > -1) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        mode[i] = -1;
                    }
                }
            }
             
            maxLen = Math.max(maxLen, dp[i]);
        }
         
        return dp[nums.length - 1];
    }
}

O(n) time solution:

Leetcode 375. Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Analysis:
The problem can be done by DFS + memorization.
Note that the problem asks for the worst case scenario since you need to guarantee a win. In the worst case scenario, you need to guess wrong for each time expect for there is only 1 number.

Code (Java):

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
         
        getMoneyAmountHelper(1, n, dp);
         
        return dp[1][n];
    }
     
    private int getMoneyAmountHelper(int start, int end, int[][] dp) {
        if (start >= end) {
            return 0;
        }
         
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
         
        int minCost = Integer.MAX_VALUE;
        for (int i = start; i <= end; i++) {
            int cost = i + Math.max(getMoneyAmountHelper(start, i - 1, dp), 
                                    getMoneyAmountHelper(i + 1, end, dp));
            minCost = Math.min(minCost, cost);
        }
         
        dp[start][end] = minCost;
         
        return minCost;
    }
}

Leetcode 368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

Analysis:
The idea is the same as LIS.

Code (Java):

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
         
        Arrays.sort(nums);
         
        int[] dp = new int[nums.length];
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max, dp[i]);
                }
            }
        }
         
        // print the largest set
        //
        int i = nums.length - 1;
        while (i >= 0 && dp[i] != max) {
            i--;
        }
         
        ans.add(nums[i]);
        i--;
        max--;
         
        while (i >= 0) {
            if ((ans.get(ans.size() - 1) % nums[i]) == 0 && dp[i] == max) {
                ans.add(nums[i]);
                max--;
            }
            i--;
        }
         
         
        return ans;
    }
}

Tuesday, September 25, 2018

Leetcode 357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:

Input: 2
Output: 91 
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, 
             excluding 11,22,33,44,55,66,77,88,99

Code (Java):

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n >= 11) {
            return 0;
        }
         
        int ans = 1;
         
        for (int i = 1; i <= n; i++) {
            int factor = 9;
            int num = 9;
            for (int j = 2; j <= i; j++) {
                num *= factor;
                factor--;
            }
            ans += num;
        }
         
        return ans;
    }
}

Note:
1. The most significant bit can't be 0, so it can only be 1 to 9, so the second bit has 9 possible digits.

2. n can be at most 10. If n is greater than 10, the result will be 0. That's because of the pigeonhole theory.

Leetcode 908. Smallest Range I

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to A[i].

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 0
Explanation: B = [3,3,3] or B = [4,4,4]

Note:

1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

Code (Java):

class Solution {
    public int smallestRangeI(int[] A, int K) {
        if (A == null || A.length < 2) {
            return 0;
        }
         
        Arrays.sort(A);
         
        int ans = 0;
         
        if (A[0] + K >= A[A.length - 1] - K) {
            return 0;
        } else {
            return A[A.length - 1] - K - A[0] - K;
        }
    }
}

Thursday, September 6, 2018

Leetcode 394. Decode String

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution:
Use two stacks. One store the number, another store the previous partial result.

Code (Java):

class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
         
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
         
        String ans = "";
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    int digit = Character.getNumericValue(s.charAt(i));
                    num = num * 10 + digit;
                    i++;
                }
                 
                numStack.push(num);
            } else if (c == '[') {
                strStack.push(ans);
                i++;
                ans = "";
            } else if (c == ']') {
                int num = numStack.pop();
                StringBuilder sb = new StringBuilder(strStack.pop());
                for (int r = 0 ; r < num; r++) {
                    sb.append(ans);
                }
                 
                ans = sb.toString();
                i++;
            } else {
                ans += c;
                i++;
            }
        }
         
        return ans;
    }
}

Wednesday, September 5, 2018

Leetcode 366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2

2. Now removing the leaf [2] would result in this tree:

3. Now removing the leaf [1] would result in the empty tree:

[]

Solution:
DFS + backtracking. Get depth of each node, and group the nodes with the same depth together.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
         
        if (root == null) {
            return ans;
        }
         
        findLeavesHelper(root, ans);
         
        return ans;
    }
     
    private int findLeavesHelper(TreeNode root, List<List<Integer>> ans) {
        if (root == null) {
            return -1;
        }
         
        int left = findLeavesHelper(root.left, ans);
        int right = findLeavesHelper(root.right, ans);
         
        int depth = Math.max(left, right) + 1;
         
        if (depth == ans.size()) {
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            ans.add(list);
        } else {
            List<Integer> list = ans.get(depth);
            list.add(root.val);
        }
         
         
        return depth;
    }
}

Leetcode 364. Nested List Weight Sum II

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.

Example 2:

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

Code (Java):

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    private int maxDepth = 0;
    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return 0;
        }
         
        getDepth(1, nestedList);
         
        return depthSumHelper(maxDepth, nestedList);
    }
     
    private void getDepth(int level, List<NestedInteger> nestedList) {
        maxDepth = Math.max(maxDepth, level);
        for (NestedInteger n : nestedList) {
            if (!n.isInteger()) {
                getDepth(level + 1, n.getList());
            }
        }
    }
     
    private int depthSumHelper(int depth, List<NestedInteger> nestedList) {
        int sum = 0;
        for (NestedInteger n : nestedList) {
            if (n.isInteger()) {
                sum += depth * n.getInteger();
            } else {
                sum += depthSumHelper(depth - 1, n.getList());
            }
        }
         
        return sum;
    }
}

Monday, September 3, 2018

Leetcode: Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

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

Understand the problem: