Leetcode/G家 -- 159. Longest Substring with At Most Two Distinct Characters(window 2 ptr)

159. Longest Substring with At Most Two Distinct Characters (window 2 ptr)
Hard
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

思路： Use window method, counter to track distinct character, when counter > 2, remove one distinct character(till count = 0) to track next substring.

public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        int counter = 0, len = 0;
        while(end < s.length()){
            char cur = s.charAt(end);
            if(!map.containsKey(cur)) map.put(cur, 0);
            map.put(cur, map.get(cur) + 1);
            if(map.get(cur) == 1) counter++;//new distinct char
            while(counter > 2){//
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) - 1);
                if(map.get(c2) == 0) counter--;
                start++;
            }
            len = Math.max(end - start + 1, len);
            end++;
        }
        return len;
    }

Leetcode/各大家 -- 101. Symmetric Tree(Recur + Itera)

101. Symmetric Tree (Recursion + Iteration)


easy
https://leetcode.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

LinkedIn Bloomberg Microsoft



思路： use recursion to recursively find if nodes in left & right subtree match till leaves.
               helper(left.left ,right.right) && helper(left.right, right.left);

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return helper(root.left, root.right);
    }
    private boolean helper(TreeNode leftN, TreeNode rightN){
        if(leftN == null || rightN == null)
            return leftN == rightN;//need both be null
        if(leftN.val != rightN.val)
            return false;
        return helper(leftN.left, rightN.right) && helper(leftN.right, rightN.left);
    }
}

Leetcode/亚麻 -- 438. Find All Anagrams in a String (window2ptr)

438. Find All Anagrams in a String(window 2ptr)
easy
https://leetcode.com/problems/find-all-anagrams-in-a-string/

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

思路： string window套路 using 2 pointer, key is to check 'end - start + 1 == t.length()' to find valid anagram.
Complexity: O(N) time - loop, O(N) space - map

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> res = new ArrayList<Integer>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();//<all char, freq in t>
        for(char c : s.toCharArray()) map.put(c, 0);
        for(char c : t.toCharArray()){
            if(map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else 
                return res;
        }
        int start = 0, end = 0;
        int counter = t.length();
        while(end < s.length()){
            char cur = s.charAt(end);
            if(map.get(cur) > 0) counter--;
            map.put(cur, map.get(cur) - 1);
            while (counter == 0){
                if(end - start + 1 == t.length()) res.add(start);
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) + 1);
                if(map.get(c2) > 0) counter++;
                start++;
            }
            end++;
        }
        return res;
    }
}

Leetcode -- 338. Counting Bits(DP)

338. Counting Bits(DP)
medium
https://leetcode.com/problems/counting-bits/

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

思路： use dp, find the relation that dp[i] = dp[i-offset] + 1, offset: 0,1,2,4,8..
          eg dp[4] = d[4-4]+1 = 1, dp[6] = dp[6-4] + 1 = dp[2] + 1 = 2
Complexity:  time-O(N), SpaceO(N)

public class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        int offset = 1;
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            if(offset * 2 == i) offset = i;
            dp[i] = dp[i - offset] + 1;
        }
        return dp;
    }
}

Leetcode/F家微软 -- 91. Decode Ways(DP)

91. Decode Ways(DP)
medium
https://leetcode.com/problems/decode-ways/ 

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 Microsoft Uber Facebook

思路： use dp to add through string. Prefill dp[0] 1. For  current char,
1 - If cur.val != 0, dp[i+1](cur) = dp[i](pre) - inherit last char (we treat cur as one letter)
2 - If cur.val + pre.val * 10 in [10,26], dp[i+1] += dp[i-1] - add 2nd last char(we treat cur&last as one letter)
Complexity: Time O(n) Space O(n)

//invalid case: 001, 1001 ..., return 0
    public int numDecodings(String s) {
        if(s.length() == 0||s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];//need prefill 2 val in dp
        dp[0] = 1;//default val
        dp[1] = 1;//filled by 1st char in s
        for(int i = 1; i < s.length(); i++){
            int pre = s.charAt(i-1) - '0';
            int cur = s.charAt(i) - '0';
            if(cur != 0){//no char for single 0
                dp[i+1] = dp[i];
            }
            int sum = pre*10 + cur;
            if(sum >= 10 && sum <=26){//eg:01 not valid, only bt [10,26]
                dp[i+1] += dp[i-1];
            }
        }
        return dp[dp.length - 1];
    }

/*125  127
  ABE   ABG 
   LE    LG
   AY   
----------
   3     2 
*/

Leetcode/各大家 -- 57. Insert Interval(Array Sort)

57. Insert Interval(Array)
hard
https://leetcode.com/problems/insert-interval/ 

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

LinkedIn Google Facebook

思路： Merge when curInterval.end >  newInterval.start && curInterval.start <= newInterval.end
            Merge the newInterval with old one into newInterval  by keep the min as start, max as end.
            Do it in place by remove the old ones that are merged, watch index(i), no need to modify.
            And finally insert interval to result.
Complexity: O(N)time, O(1)space

/**
 * 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> insert(List<Interval> intervals, Interval newInterval) {
        int i = 0;
        // add all the intervals ending before newInterval starts
        while(i < intervals.size() && intervals.get(i).end < newInterval.start)
            i++;
        // merge all overlapping intervals to one considering newInterval
        while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
            newInterval = new Interval( 
                Math.min(intervals.get(i).start, newInterval.start),
                Math.max(intervals.get(i).end, newInterval.end));
            intervals.remove(i);//no modify i since removal(i), so next loop i will get next element in list
        }
        intervals.add(i, newInterval);
        return intervals;
    }
}

Leetcode/F家 -- 398. Random Pick Index(Desgin + Random)

398. Random Pick Index(Design + Random)
Medium
https://leetcode.com/problems/random-pick-index/ 

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

思路： use random to ensure equal possibility, key point is save extra space.
解法1: for easier understanding, we create arraylist to store all index of target, and count total,
           Then we use random  from [0,total), to equally pick any element in the array 
Complexity: O(N)time O(m)space - # of target in nums

public class Solution {
    int[] nums;
    Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    public int pick(int target) {
        int total = 0;//total index match target
        int res = -1;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                total++;
                list.add(i);
            }
        }
        res = list.get(rand.nextInt(total)); //int in [0,total)
        return res;
    }
}

解法2: To use no extra space, we pick the index in place.
             (Reservoir Sampling) update by 1/total in the loop
             靠前的index一开始选中的几率高，但是后面loop剩的多被replace的几率也高
             举例有5个元素：
             对于第二个index来说，1/2（pick）*2/3(replace)*3/4(replace)*4/5(replace) = 1/5;
             对于最后一个index来说，就是 1/5(pick) = 1/total.

public class Solution {
    int[] nums;
    Random rand;
    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }
    public int pick(int target) {
        int total = 0;//total index match target
        int res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                total++;
                int x = rand.nextInt(total);//[0,total)
                if(x == 0){
                    res = i;
                }
            }
        }
        return res;
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

Leetcode/微软 -- 116. Populating Next Right Pointers in Each Node(Recur + Iterat)

116. Populating Next Right Pointers in Each Node(Recursion+ Iteration)
medium
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

思路1： use recursion,
Complexity: O(n)time  --  visit each node to set up next pointer.
                     O(logN) space -- each node up to logN nodes from ancestor to itself

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)return;
        if(root.left != null){
            root.left.next = root.right;
            if(root.next != null){
                root.right.next = root.next.left;//perfect binary tree, no check if root.right is null
            }
        }
        connect(root.left);
        connect(root.right);
    }
}

思路2: Iterative, need to check cur.next is null, eg rightmost node on level
Complexity: O(N)-time O(1)-space

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)return;
        TreeLinkNode level_start=root;
        while(level_start != null){
            TreeLinkNode cur=level_start;
            while(cur != null){
                if(cur.left != null)cur.left.next = cur.right;
                if(cur.right != null && cur.next != null)cur.right.next = cur.next.left;
                cur = cur.next;
            }
            level_start = level_start.left;
        }
    }
}