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