Leetcode/各大家 -- 377. Combination Sum IV(DP)

377. Combination Sum IV (DP)
medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Google Snapchat Facebook

思路1：DP - Fill each dp[i] from 0 to target indicating the possibilites to sum to i;
          To fill each dp[i], we check through nums and pick any of element possible, at which it has target dp[target-nums[i]] possibility

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){//fill dp[i], indicates ways to sum to i
            for(int j = 0; j < nums.length; j++){//calculate each dp[i]
                if(i - nums[j] >= 0){
                    dp[i] += dp[i - nums[j]];  
                } 
            }
        }
        return dp[target];
    }
}

eg:
nums[1,2,3] target = 4

dp[0, 1, 2, 3, 4] return dp[4]
   1, 1, 2, 4, 7
dp[4] = dp[4-1] + dp[4-2] + dp[4-3] = dp[3] + comb[2] + comb[1].
7 is from  1(dp of nums[0] = dp[1])+2(dp of nums[1])+4(dp of nums[2])
To get 4, when at dp[4], we can choose any num[i] in nums and so it will have target-nums[i] possibility

思路2： top-down recursion with hashmap
https://discuss.leetcode.com/topic/52255/java-recursion-solution-using-hashmap-as-memory

Leetcode -- 216. Combination Sum III (Backtracking)

216. Combination Sum III (Backtracking)

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

思路： use backtracking to find all possible solutions.
Complexity: Time O(9!) - total possibilities Space O(9) stack

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>> ();
        dfs(1, n, k, new ArrayList(), res);
        return res;
    }
    
    private void dfs(int start, int n, int k, List<Integer> path, List<List<Integer>> res){
        if(path.size() == k){
            if(n == 0)res.add(new ArrayList(path));
            return;
        }
        for(int i = start; i <= 9; i++){//digits from 1 to 9
            path.add(i);
            dfs(i + 1, n - i, k, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Leetcode/各大家 -- 56. Merge Interval(Comparator)

56. Merge Intervals(Comparator)
medium
https://leetcode.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18]. 

 LinkedIn Google Facebook Twitter Microsoft Bloomberg Yelp

思路： Use Collections.sort to sort interval by start time using comparator.
           Then loop through each interval, when there pre end >= new start(intersection), merge it.
           Else add the pre interval to list.  After loop, add the last interval to list.
Complexity: Time O(N) Space O(N)

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
         if(intervals.size() <= 1)
            return intervals;
         // Sort by ascending starting point using an anonymous Comparator
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start-i2.start;
            }
        });
        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); i++){
            int nstart = intervals.get(i).start;
            int nend = intervals.get(i).end;
            //if not disjoint set
            if(end >= nstart){
               end = Math.max(end, nend);
           }else{
                result.add(new Interval(start,end));
                start = nstart;
                end = nend;
            }
        }
        //add the last interval
        result.add(new Interval(start, end));
        return result;
    }
}

HackerRank -- count the number without repeating digits in a range

Count the number that has no repeating digits like(121,11) in a range

Given arr[][], arr[i][0]- arr[i][1] is a range.

static void countNumbers(int[][] arr) {
    Set < Integer > set = new HashSet < > ();
    for (int i = 0; i < arr.length; i++) {
        int start = arr[i][0], end = arr[i][1];
        int count = 0;
        for (int j = start; j <= end; j++) {
            if (set.contains(j)) continue;
            if (checkRepeats(j)) count++;
            else set.add(j);
        }
        System.out.println(count);
    }
}

static boolean checkRepeats(int number) {
    Set < Character > set = new HashSet < Character > (); //<digit, freq>
    String num = Integer.toString(number);
    for (Character c: num.toCharArray()) {
        if (set.contains(c)) return false;
        set.add(c);
    }
    return true;
}

Leetcode/各大家 -- 22. Generate Parentheses(Backtracking)

22. Generate Parentheses(Backtracking)
medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

 Google Uber Zenefits

思路： - use dfs, every point, it has two options '(', ')'. We have n left bracket '(', n right bracket ')',    
            - when both  left and right are used up, we add to result.
            - Watch return cases! if left > right, no valid answer. eg: )(())(
               Also we can't have > n left or right bracket
Complexity: Time O(2^n)  Space O(n)

public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        dfs(new StringBuilder(), n, n,res);
        return res;
    }
    public void dfs(StringBuilder path,int left,int right,List<String> res){
        int len = path.length();
        if(left > right || left < 0 || right < 0){
            return;
        }
        if(left == 0 && right == 0){
            res.add(path.toString());
            return;
        }
        dfs(path.append("("),left-1,right,res);
        path.setLength(len);
        dfs(path.append(")"),left,right-1,res);
        path.setLength(len);
    }

Leetcode/亚麻 -- 199. Binary Tree Right Side View (BFS + DFS)

199. Binary Tree Right Side View (BFS + DFS)
medium
https://leetcode.com/problems/binary-tree-right-side-view/

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

思路1： BFS, use level order traverlsal. key is to track each level size, and add the 1ast one to list.

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        if(root == null) return res;
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i = 0; i < size; i++){//traveling current level
                TreeNode curr = qu.remove();
                if(i == size - 1)res.add(curr.val);
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return res;
    }

思路2: DFS， preorder改一下顺序，从右走的左边. To ensure rightmost node of depth,
            Key is we ensure we only add the first node of the specific depth by check depth == list size.
for ex, if we add node at depth 1 from right subtree, we won't add it again when travel the left subtree

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(root, result, 0);
        return result;
    }
    public void traverse(TreeNode root, List<Integer> result, int depth){
        if(root == null)return;
        if(depth == result.size()){
            result.add(root.val);
        }
        traverse(root.right, result, depth + 1);
        traverse(root.left, result, depth + 1);
    }

Leetcode/各大家 -- 230. Kth Smallest Element in a BST(Recur + Ite)

230. Kth Smallest Element in a BST (Recur + Itera)
medium

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Bloomberg Uber Google

思路1： using inorder traversal by recursion, keep a global var count to track kth element.
Inorder we will first get the min(leftmost node), then 2nd min (parent node of min),
then 3rd min(right node of 2nd min)....
Complexity: O(N) - time O(N) - stack

public class Solution {
    int count = 0;
    int result = -1;
    public int kthSmallest(TreeNode root, int k) {
        traverse(root, k);
        return result;
    }
    public void traverse(TreeNode root, int k) {
        if(root == null) return;
        traverse(root.left, k);
        count++;
        if(count == k)
            result = root.val;
        traverse(root.right, k);
    }    
}

思路2： using iteration to store the path to current min node into a stack.
When we pop node, we check if it has left node and add till the leftmost node all the way to leftmost.

public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new LinkedList<>();
        int res = 0;
        while(root != null){//find the min - leftmostnode
            st.push(root);
            root = root.left;
        }
        while(!st.isEmpty() && k > 0){
            TreeNode cur = st.pop();
            res = cur.val;
            k--;
            cur = cur.right;
            while(cur != null){//keep adding till the leftmost node of right node
                st.push(cur);
                cur = cur.left;
            }
        }
        return res;
    }