398. 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);

Reservoir Sampling

public class Solution {
    int[] nums;
    Random r;

    public Solution(int[] nums) {
        this.nums = nums;
        r = new Random();
    }
    
    public int pick(int target) {
        int idx = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != target) continue;
// for the nth target, the prob of returning is 1/n
// for the (n-1)th target, the prob of returning is (n-1)/n * 1/(n-1) = 1/n
            if (r.nextInt(++count) == 0) {
                idx = i; 
            }
        }
        
        return idx;
        
    }
}
Advertisements

[summary] Graph BFS solves problems

210: Course Schedule II
269: Alien Dictionary
题目描述见网站

210: 课程的dependency本来就存在edges数组表示,可以转换成map方便访问,然后对graph进行bfs
269: 从dict中抽出字母先后顺序,字母组成一个graph,对graph进行bfs

bfs的过程:

Queue先存入in degree为0的点
当queue不为空时:
取出点,加入结果
此点在map中指向的所有下一个点,给他们的in degree都减1
此时in degree为0的点重新加入queue

其实是有顺序的bfs,顺序为先访问dependency最小的点。这个方法两道题都可以解决。

132. Palindrome Partitioning II

从夏威夷回来又休息了几天,继续做题继续更博。

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

public int minCut(String s) {
        int n = s.length();
        int[] cut = new int[n+1];
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            // check odd length palindrome
            for (int j = 0; i-j >=0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++) {
                cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j]);
            }
            
            // check even length palindrome
            for (int j = 0; i-j >= 0 && i+j+1 < n && s.charAt(i-j) == s.charAt(i+j+1); j++) {
                cut[i+j+2] = Math.min(cut[i+j+2], 1+cut[i-j]);
            }
        }
        
        return cut[n];
    }

DP题目有时候思路很简单很对称。这道题的基本思路如下:
假设 a b a c
用一个数组表示截止到每个字母(字母前)有几个cut
初始值为:
str = [a b a c]
cut = [0 1 2 3]

以第i个字母为中心,check它左右对称位置的字母是否相等,如果相等,则组成了palindrome,那么cut就应该相应的减少。

例如在b的位置, i = 1, str[i-1] == str[i+1], 所以在i+1这个位置的后面,即cut[i+2],cut数变成min(cut[i+2], cut[i-1] + 1)
[a, b, a, c]
[0, 1, 2, 1]

以上palindrome是odd length,再举一个even length的例子
str = [b, a, a, b, c]
cut = [0, 1, 2, 3, 4]
例如在i = 1的位置 str[i-0] == str[i+0+1], str[i-1] == str[i+1+1], 所以在cut[i+3]的位置上,变成min(cut[i+3], cut[i-1] + 1)

总结以上两个例子,
odd length: i-j >= 0 && i+j = 0 && i+j+1 < cut.length && str[i-j] == str[i+j+1]情况下,
cut[i+j+2] = min(cut[i+j+2], 1+cut[i-j])。需要保证i+j+2在cut长度范围内。

注意,如果整个str就是一个palindrome,例如
str = [b, b]
对于i = 0, 只check j = 0的时候,因为需要保证i+j+1在cut长度范围内,这样就找不到palindrome了。所以cut长度选为n+1而不是n,n是str的长度。

373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

这是展示如何从最简单的方法一步步改进的例子。

首先明白一个基本问题,要找k个sum最小的pair,用heap,并且重新定义heap的compare。用java8的写法:

PriorityQueue que = new PriorityQueue((a, b) -> a[2] - b[2])

其中a[2]-b[2]这是根据把什么样的数据结构存入heap来的,不管用什么样的数据结构,让heap比较两个pair的和

接下来首先尝试brute force:

        List<int[]> ans = new ArrayList<int[]>();
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b) -> a[0] + a[1] - b[0] - b[1]);
        for (int n1 : nums1) {
            for (int n2 : nums2) {
                que.add(new int[]{n1, n2}); //在heap中存入(nums1[i], nums2[j])
            }
        }

        while (k-- > 0 && !que.isEmpty()) {
            ans.add(que.poll());
        }
        return ans;

因为两个array都是sorted,而结果只需要头k个sum最小的pair,一种改进是:先存入nums1[i] + nums2[0], i = 0,…,nums1.length-1. 对每个nums1[i], sum最小的pair除了当前已经存入(i,j)的pair之外,唯一的选择就是nums1[i] + nums2[j+1]了,将这个选择存入heap,同时从heap中取出k个pair

        List<int[]> ans = new ArrayList<int[]>();
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b) -> a[0] + a[1] - b[0] - b[1]);
        for (int n1 : nums1) {
            que.add(new int[]{n1, nums2[0], 0});
        }

        while (k-- > 0 && !que.isEmpty()) {
            int[] cur = que.poll();
            ans.add(new int[]{cur[0], cur[1]});
            if (cur[2] == nums2.length-1) continue;
            que.add(new int[]{cur[0], nums2[cur[2]+1], cur[2]+1}); //对nums1[cur[0]]来说,最小的除了nums2[cur[2]]外就是nums2[cur[2]+1]了
        }
        return ans;

不难发现其实不需要在一上来就在heap中存所有nums1[i]和nums2[0]的pair,只需要加入k个就够了,后面的都不可能在答案中。简单改进:

        List<int[]> ans = new ArrayList<int[]>();
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b) -> a[0] + a[1] - b[0] - b[1]);
        for (int i = 0; i < k && i < nums1.length; i++) {             que.add(new int[]{nums1[i], nums2[0], 0});          }                  while (k-- > 0 && !que.isEmpty()) {
            int[] cur = que.poll();
            ans.add(new int[]{cur[0], cur[1]});
            if (cur[2] == nums2.length-1) continue;
            que.add(new int[]{cur[0], nums2[cur[2]+1], cur[2]+1});
        }
        return ans;

最后一步改进比较难想。首先有一个发现:两个array每个元素相加构成了一个matrix
1 7 11
2| 3 9 13
4| 5 11 15
6| 7 13 17
按小到大排列是“/”型的:3 -> (5, 9) -> (7, 11, 13) -> (13, 15) -> 17
但按这个顺序遍历到所有,或是前k个元素?
想到了tree:
3 -> 9 -> 13

5 ->11 -> 15

7 ->13 -> 17
那么按之前的顺序遍历就成了BFS

        List<int[]> ans = new ArrayList<int[]>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) return ans;
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        que.add(new int[]{0, 0, nums1[0] + nums2[0]}); // i, j, sum
        while (k-- > 0 && !que.isEmpty()) {
            int[] cur = que.poll();
            int i = cur[0];
            int j = cur[1];
            ans.add(new int[]{nums1[i], nums2[j]});
            if (j < nums2.length - 1) {
                que.add(new int[]{i, j + 1, nums1[i] + nums2[j+1]});
            }
            if (j == 0 && i < nums1.length - 1) {
                que.add(new int[]{i + 1, j, nums1[i+1] + nums2[j]});
            } //上面tree的结构决定的

        }
        return ans;

[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;

    }