[bst] 501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

首先想到最原始的方法,并不需要利用bst的特点,直接遍历,然后存map记录每个node的个数,记住mode(即最大的)count是多少,再从map中找到所有符合mode count的node

    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap();
        int max = helper(root, map, 0);
        List<Integer> list = new ArrayList();
        for (int val : map.keySet()) {
            if (map.get(val) == max) {
                list.add(val);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        
        return res;
    }
    
    private int helper(TreeNode root, Map<Integer, Integer> map, int max) {
        if (root == null) return max;
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        max = Math.max(max, map.get(root.val));
        if (root.left != null) {
            int lmax = helper(root.left, map, max);
            max = Math.max(max, lmax);
        }
        
        if (root.right != null) {
            int rmax = helper(root.right, map, max);
            max = Math.max(max, rmax);
        }
        
        return max;
    }

比较啰嗦,运行速度慢,还需要extra space

因为follow up中要求不能使用extra space。想到bst是可以按大小顺序遍历tree的,如果需要排序,则需要inorder遍历。这样遍历一遍就可以知道mode的count是多少,有几个。再遍历第二遍,找到符合mode count的node即可。

    int curval = 0;
    int curcount = 0;
    int[] mode;
    int maxcount = 0;
    int modecount = 0;
    public int[] findMode(TreeNode root) {
        first(root);
        mode = new int[modecount];
        curcount = 0;
        modecount = 0;
        second(root);
        return mode;
    }
    
    private void first(TreeNode root) {
        if (root == null) return;
        first(root.left);
        
        // handle value
        int val = root.val;
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        if (curcount > maxcount) {
            maxcount = curcount;
            modecount = 1;
        } else if (curcount == maxcount) {
            modecount++;
        }
        first(root.right);
        
    }
    
    private void second(TreeNode root) {
        if (root == null) return;
        second(root.left);
        
        // handle value
        int val = root.val;
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        
        if (curcount == maxcount) {
            mode[modecount] = curval;
            modecount++;
        }
        
        second(root.right);
    }

space,time complexity都提高了,code很啰嗦,再improve一下,发现两个pass的handle value部分都差不多,合并成一个

    int curval = 0;
    int curcount = 0;
    int[] mode;
    int maxcount = 0;
    int modecount = 0;
    public int[] findMode(TreeNode root) {
        inorder(root);
        mode = new int[modecount];
        curcount = 0;
        modecount = 0;
        inorder(root);
        return mode;
    }
    
    private void handleval(int val) {
        if (curval != val) {
            curval = val;
            curcount = 0;
        }
        curcount++;
        if (curcount > maxcount) {
            maxcount = curcount;
            modecount = 1;
        } else if (curcount == maxcount) {
            if (mode != null) {
                mode[modecount] = curval;
            }
            modecount++;
        }
    }
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        handleval(root.val);
        inorder(root.right);
    }

[dfs] 473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

想到的部分:把所有数字分为4组,使每组和为sum / 4。如果sum % 4 != 0 或者一共有小于4个数字就不可能形成正方形。分组的过程用dfs。
没想清楚的部分:dfs怎么实现。

public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) return false;
    int total = 0;
    for (int num : nums) total += num;
    if (total % 4 != 0) return false;
    return dfs(nums, total / 4, new int[4], 0);
}
    
private boolean dfs(int[] nums, int target, int[] sums, int index) {
    if (index == nums.length) {
        if (sums[0] == target && sums[1] == target && sums[2] == target) return true;
        return false;
    }
        
    for (int i = 0; i < 4; i++) { //尝试当前数字要加到哪个组
        if (sums[i] + nums[index] > target) continue;
        sums[i] += nums[index];
        if (dfs(nums, target, sums, index + 1)) return true;
        sums[i] -= nums[index];
    }
        
    return false;
}

本题需要找到4个sum,其实相对找到1个sum,增加的复杂度并不大,以下是另外一种实现,更加直接。
另,本来想到了,但是没有好好加进去的optimization:先sort数组,从最大数字开始尝试,这样如果不行会尽早发现。

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int total = 0;
        for (int num : nums) total += num;
        if (total % 4 != 0) return false;
        Arrays.sort(nums);
        long sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
        return dfs(nums, total / 4, sum1, sum2, sum3, sum4, nums.length - 1);
    }
    
    private boolean dfs(int[] nums, int target, long sum1, long sum2, long sum3, long sum4, int i) {
        if (sum1 > target || sum2 > target || sum3 > target || sum4 > target) return false;
        if (i == -1 && sum1 == target && sum2 == target && sum3 == target) return true;
        else if (i == -1) return false;
        
        return dfs(nums, target, sum1+nums[i], sum2, sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2+nums[i], sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3+nums[i], sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3, sum4+nums[i], i-1);
    }

[bit manipulation] 421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example: Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28. 分别计算每一位应该是什么

 public int findMaximumXOR(int[] nums) {        int max = 0, mask = 0;        for (int i = 31; i >= 0; i--) { //从最重要的位MSB看起
           mask = mask | 1 << i; // 每次只看一位,用mask控制看哪位
           Set<Integer> set = new HashSet();
           for (int num : nums) {
               set.add(num & mask); //记录所有nums在这一位是什么情况
           }
           int tmp = max | (1 << i); //结果在当前位暂时设为1
           for (int prefix : set) {
               if (set.contains(tmp ^ prefix)) {
                   max = tmp; //如果有在这一位有和max不同的,那么max在这一位就真的可以是1
                   break;
               }
           }
       }
       return max;

    }

[bit manipulation]477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

Brute force: time limit exceed
思路:integer一共32位, int[] count = new int[32]记录每个bit一共在几个数字中on(一共n = nums.length个数字)。对于一个bit,on的次数 k 次,off的次数 n-k 次,则对于total distance的贡献是 k * (n-k),因为每一个(on, off)的组合都会给total distance加1.

    public int totalHammingDistance(int[] nums) {
        int N = nums.length;
        int[] count = new int[32]; // count for when the bit is on
        for (int n : nums) {
            int i = 0;
            while (n > 0) {
                count[i++] += n & 1;
                n >>= 1;
            }
        }
        
        int total = 0;
        for (int i = 0; i < 32; i++) {
            total += count[i] * (N - count[i]);
        }
        return total;
    }

[LC 456]. 132 Pattern

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. Note: n will be less than 15,000. Example: Input: [-1, 3, 2, 0] Output: True Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Example [9, 11, 8, 9, 10]

Step 1 — stack is empty, save pair (9,9)

Step 2 — 11 > stack.peek().min, last pair = stack.pop(), 11 > last.max, last = (9,11), stack is empty, save pair (9,11)

Step 3 — 8 < stack.peek().min, save (8,8)

Step 4 — 9 > stack.peek().min, last = stack.pop(), 9 > last.max, last = (8,9) and does not cover or overlap with stack.peek(), which is (9,11), save (8,9). Stack is now [(9,11), (8,9)]

Step 5 — 10 > stack.peek().min, last = (8,9), 10 > last.max, last = (8,10) and does not cover stack.peek(), which is (9,11). But 10 is in (9,11), return true.

public class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Pair> stack = new Stack();
        for (int n : nums) {
            if (stack.isEmpty() || n < stack.peek().min) {                 stack.push(new Pair(n,n));             } else if (n > stack.peek().min) {
                Pair last = stack.pop();
                if (n < last.max) return true;
                else {
                    last.max = n;
                    while (!stack.isEmpty() && last.min <= stack.peek().min && last.max >= stack.peek().max) stack.pop(); // cover previous pair
                    if (!stack.isEmpty() && last.max < stack.peek().max && last.max > stack.peek().min) return true; // overlap with previous pair
                    stack.push(last);
                }
            }
        }

        return false;
    }
}
class Pair {
    int min;
    int max;
    public Pair(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

[LC 330]. 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:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4]

用一个例子说明思路:
nums = [1, 2, 4, 13, 43], n = 100
miss — Smallest miss sum, i.e. sum in the range [0, miss) has been reached
miss = 1, nums[0] = 1, [0, 2) can be reached, miss -> 2
miss = 2, nums[1] = 2, [0, 4) can be reached, miss -> 4
miss = 4, nums[2] = 4, [0, 8) can be reached, miss -> 8
miss = 8, nums[3] = 13, add 8, [0, 16) can be reached, miss -> 16
miss = 16, nums[3] = 13, [0, 29) can be reached, miss -> 29
miss = 29, nums[4] = 43, add 29, [0, 58) can be reached, miss -> 58
miss = 58, nums[4] = 43, [0, 101) can be reached, miss -> 101 > 100

Added 2 numbers in total

    public int minPatches(int[] nums, int n) {
        long miss = 1; // n = Integer.MAX_VALUE时会用到long
        int i = 0, count = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                count++;
                miss += miss;
            }
        }
        
        return count;
    }

[LC 316]. Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given “bcabc”
Return “abc”

Given “cbacdcbc”
Return “acdb”

两种思路:
1, recursive
搜索最左边的最小的character,如果出现已经错过了某个character所有出现的位置,那么暂停搜索。删除找到的character和它左边所有的character,再来继续重复以上操作.
举例:caccabad
第一步找到a,继续搜索cccbd
第二步找到c,继续搜索bd
第三步找到b,继续搜索d
第四步找到d

    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0) return s;
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--count[s.charAt(i) - 'a'] == 0) break;
        }
        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }

2,iterative
找到所有字幕最后一次出现的位置,从位置最靠前的开始搜索范围内最小的character。
举例:cbacdcbc
abcd最后出现的位置 [2, 6, 7, 4]
第一步搜索[0, 2],找到’a’,s[2] == ‘a’,end = 4
第二步搜索[3, 4],找到’c’,s[4] != ‘c’,end不变
第三步搜索[4, 4],找到’d’,s[4] == ‘d’,end = 6
第四步搜索[5, 6],找到’b’,s[6] == ‘b’,end = 7
结果长度已经够了,停止搜索

    public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        Arrays.fill(lastIndex, -1);
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (lastIndex[c - 'a'] < 0) len++;
            lastIndex[c - 'a'] = i;
        }
        
        StringBuilder sb = new StringBuilder();
        int start = 0, end = getMin(lastIndex);
        while (sb.length() < len) {
            char minChar = 'z' + 1;
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if (lastIndex[c - 'a'] >= 0 && c < minChar) {//已经加入的就不算了
                    minChar = c;
                    start = i+1; //下个start在找到的最小字母后
                    
                }
            }
            
            sb.append(minChar);
            lastIndex[minChar - 'a'] = -1; //已经加入的字母就记录成没有
            
            if (s.charAt(end) == minChar) end = getMin(lastIndex); //条件
        }
        
        return sb.toString();
        
    }
    private int getMin (int[] array) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0) continue;
            if (array[i] < min) {
                min = array[i];
            }
        }

        return min;
    }

两种解法都是O(n),但第一个是O(26n),第二个是O(2n),第二个快

[LC 452]. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

只需要注意一个小问题:if new interval has overlap with the template interval, the new template interval should be the narrower between the two.

See line:

if (points[i][0] <= end) end = Math.min(end, points[i][1]);

    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0 || points[0].length == 0) return 0;
        Arrays.sort(points, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) return a[1] - b[1];
                else return a[0] - b[0];
            }
        });

        int count = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= end) {
                end = Math.min(end, points[i][1]);
            } else {
                count++;
                end = points[i][1];
            }
        }
        return count;
    }

[LC 240]. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

从top right corner开始,如果 target 就向左移一列。

从2D的角度,也是一种binary search

好好想算法就能很简单的一道题

有趣的是,[LC 74]. Search a 2D Matrix也可以用一摸一样的code解决,虽然这道题有多种不同的解法,例如treat 2D array as 1D.

以下是这段通用的code

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0) {
             if (matrix[i][j] == target) return true;
             else if (matrix[i][j] < target) {
                 i++;
             } else {
                 j--;
             }
        }
        
        return false;
    }

对74,另外一种1D的做法(要点:a[i] -> A[i/cols][i%cols])

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = m * n - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (matrix[mid / n][mid % n] < target) {
                i = mid + 1;
            } else if (matrix[mid / n][mid % n] > target) {
                j = mid - 1;
            } else {
                return true;
            }
        }
        return false;
 
    }

[Summary] contains duplicate I, II, III

I – Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

II – Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

III – Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

解题思路:
I – 用set记录是否出现重复的数字
if (!set.add(nums[i])) return true

II – 用set,但超出|i-j| k) set.remove(nums[i-k-1])

III – basic idea: 用bucketing,例如t = 3,将[0,1,2,3]对应到0,[4,5,6,7]对应到1,…这样和某一个数字相差<=3的数字,一定在自己对应的bucket,或相邻的bucket中。因此mapping function: nums[i] / (t+1).
details:
1.问题:nums[i]可能<0, [-3,-2,-1,0]和[0,1,2,3]在经过bucket mapping之后,都将对应到0. 解决办法:nums[i] = (long)nums[i] – Integer.MIN_VALUE,让所有数字都从0开始。
2.bucket size选t+1,如果选t的话,t可能是0

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2 || k < 1 || t < 0) return false;
        Map<Long, Long> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            long rep = (long) nums[i] - Integer.MIN_VALUE;
            long bucket = rep / ((long)t + 1);
            if (map.containsKey(bucket) ||
                (map.containsKey(bucket + 1) && map.get(bucket+1) - rep <= t) ||
                (map.containsKey(bucket - 1) && rep - map.get(bucket-1) <= t)) {
return true;
}
if (map.size() >= k) {
                long lastbucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long)t + 1);
                map.remove(lastbucket);
            }

            map.put(bucket, rep);
        }

        return false;

    }