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;

    }

[LC 371]. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

位运算总结:

全的 https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
加减 https://discuss.leetcode.com/topic/49771/java-simple-easy-understand-solution-with-explanation/2

位运算做数学运算

Set union A | B
Set intersection A & B
Set subtraction A & ~B
Set negation ALL_BITS ^ A or ~A
Set bit A |= 1 << bit
Clear bit A &= ~(1 << bit)
Test bit (A & 1 << bit) != 0
Extract last bit A&-A or A&~(A-1) or x^(x&(x-1))
Remove last bit A&(A-1)
Get all 1-bits ~0

加:

public int getSum(int a, int b) {
	if (a == 0) return b;
	if (b == 0) return a;

	while (b != 0) {
		int carry = a & b;
		a = a ^ b;
		b = carry << 1;
	}

	return a;
}

减:

public int getSubtract(int a, int b) {
	while (b != 0) {
		int borrow = (~a) & b;
		a = a ^ b;
		b = borrow << 1;
	}

	return a;
}

取反:

public int negate(int x) {
	return ~x + 1;
}

[LC 406]. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Example:
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

一开始想到先按h从小到大sort,h相等时按k从小到大sort,然后再调整每个(h, k).例如example中先sort成[[4,4], [5,0], [5,2], [6,1], [7,0], [7,1]]. 但是在调整的过程中,每次把一个元素往后移,都会影响到后面的元素,这样每个元素调整的时候都需要看前面所有的元素。

然后看到一种思路:先按h从大到小sort,h相等按k从小到大sort。换个说法,先取h最大的,按k排列好,再取倒数第二大的,按k插入,一次类推。例如example中:
1.[[7,0], [7,1]]
2.[[7,0], [6,1], [7,1]] 注:(6,1)中k=1,所以插入index=1的位置,因为保证已进入的元素都>=6
3.[[5,0], [7,0], [5,2], [6,1], [7,1]] 注:插入[5,0]到index=0,然后[5,2]到index=2,因为所有之前已进入的元素都>=5

    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>(){
           public int compare(int[] a, int[] b) {
               if (a[0] == b[0]) return a[1] - b[1];
               else return b[0] - a[0];
           } 
        });
        
        List<int[]> res = new ArrayList<int[]>();
        for (int i = 0; i < people.length; i++) {
            int[] hk = people[i];
            res.add(hk[1], hk);
        }
        
        return res.toArray(new int[people.length][]);
    }

[LC 435]. Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

两点:
1.sort intervals by their ends. Why not starts? Draw a picture with some overlapping intervals and see.

a |________|
b |_________|
c |_________|
If interval a overlap with b, dump b, and check a and c. Because if c overlap with a, it will overlap with b for sure (if c.start < a.end, then c.start a.end). However if sort by start, when a and b overlap, need to check both pair (a, c) and (b, c), since the following case is possible:
a |___________|
b |__|
c |______|

2.finding minimum number of intervals to be removed, equals to finding max number of non-overlapping intervals

    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length < 2) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.end - i2.end;
            }
        });
        
        int count = 1; // max number of non-overlapping intervals
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start >= end) {
                end = intervals[i].end;
                count++;
            }
        }
        
        return intervals.length - count;
    }