代码随想录训练营第三十天 | 452. 用最少数量的箭引爆气球 435. 无重叠区间 763.划分字母区间

452. 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) { // 每一只箭尽可能射最多的气球
        // 排序：按照start
        Arrays.sort(points, (a, b) -> a[0]-b[0]);
        
        int res = 0;
        int i=0;
        while(i<points.length){
            int start = points[i][0], end = points[i][1]; // 重叠范围，每射出一箭之后会更新
            while(i<points.length){
                start = Math.max(start, points[i][0]);
                end = Math.min(end, points[i][1]);

                if(start>end) break;
                else i++;
            }
            res++;
        }
        return res;
    }
}

代码随想录解法：

1. 重叠的比较：cur的起始位置，大于pre的终止位置——而这个所谓的pre终止位置会更新……，是前面这一组重叠的气球的最小的终止位置。如果是新的一组起始的气球就不更新了。
2. Integer.compare

/**
 * 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度
 * 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间
 */
class Solution {
    public int findMinArrowShots(int[][] points) {
        // 根据气球直径的开始坐标从小到大排序
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;  // points 不为空至少需要一支箭
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着，注意这里不是>=
                count++; // 需要一支箭
            } else {  // 气球i和气球i-1挨着
                points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界
            }
        }
        return count;
    }
}

435. 无重叠区间

看起来与上一题有点像，但是这一题需要去掉特定区间。

我理解的贪心：需要去掉和其他区间重叠多的，但其实不是。

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。

1. 对于区间1：可找到对应的重叠于区间1的——1，2，3
2. 接下来就是区间4：可找到对应的重叠于区间4的——4，5
3. 区间6：……

总而言之，本题其实是要求出，重叠的组数。
也正因此，按照右区间排序，取第一个作为本组会被留下来的区间——本组的其他区间都会被删除。
最终，1、4、6不会重叠。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int i = 0;
        int res = 0;
        
        while(i<intervals.length){
            int right = intervals[i][1];
            i++;
            res++;
            while(i<intervals.length){
                if(intervals[i][0] >= right) break;
                i++;
            }
        }
        return intervals.length - res;
    }
}

763.划分字母区间

类似于上两道题：随着遍历，逐步更新边界。

class Solution {
    public List<Integer> partitionLabels(String s) { // 贪心：囊括区间内所有字母
        LinkedList<Integer> result = new LinkedList<>();
        
        // 求出每个字母的边界
        int[] edge = new int[26];
        for(int i=0; i<s.length(); i++){
            edge[s.charAt(i)-'a'] = i;
        }

        int i=0;
        int pre = 0;
        while(i<s.length()){
            int right = edge[s.charAt(i)-'a']; // 每组的边界
            while(i<s.length()){
                if(right == i++) {
                    result.add(right-pre+1);
                    pre = i;
                    break;
                }
                right = Math.max(right, edge[s.charAt(i)-'a']);
            }
        }
        return result;
    }
}

代码随想录版本：只用了一层循环，逻辑更清晰一点。

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;
        int last = -1;
        for (int i = 0; i < chars.length; i++) {
            idx = Math.max(idx,edge[chars[i] - 'a']);
            if (i == idx) {
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}