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

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

思路：以前做过最大不相交子序列的题，这次也是往这根据某一端排序的思路想的，排序后如下图，只需要维护一个公共序列的右边界r就可以了，下一次判断时，只需要判断子区间的左边是否小于r。

这个题有点坑的是使用Arrays排序，如果使用昨天的方法：

        Arrays.sort(points,(a,b)->{
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

就会出现数据溢出，使用Integer自己compare函数就不会啦，完整代码如下：

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b)-> Integer.compare(a[0], b[0]));
        int r = points[0][1];
        int result = 1;
        for(int i = 1;i < points.length;i++){
            if(points[i][0] <= r){
                r = Math.min(r,points[i][1]);
            }else{
                result++;
                r = points[i][1];
            }
        }
        return result;
    }
}

详细解说：代码随想录

435. 无重叠区间

思路：维护右边界，详细看这里：代码随想录

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 1)
            return 0;
        Arrays.sort(intervals,(a,b)-> Integer.compare(a[1],b[1]));
        int result = 0;
        int r = intervals[0][1];
        for(int i = 1;i < intervals.length;i++){
            //说明重叠了
            if(intervals[i][0] < r){
                result++;
            }else{
                // 不重叠就更新一下
                r = intervals[i][1];
            }
        }
        return result;
    }
}

763.划分字母区间

思路：根据字母划分出区间，然后将区间排序，然后求最大不相交子区间的长度。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[][] range = new int[26][2];
        // 初始化，便于后面对左区间进行赋值
        for(int i = 0;i < 26;i++){
            range[i][0] = -1;
        }
        //确定左右区间，因为for是往后遍历的，所以右区间直接取最新的就好了：range[index][1] = i;
        for(int i = 0;i < s.length();i++){
            int index = s.charAt(i) - 'a';
            if(range[index][0] == -1)
                range[index][0] = i;
            range[index][1] = i;
        }
        //按照右区间进行排序
        Arrays.sort(range,(a,b) -> Integer.compare(a[0],b[0]));
        //找到第一个有效的字母区间
        int left = 0;
        while(range[left][0] == -1)
            left++;
        //求不相交的子区间
        int l = range[left][0],r = range[left][1];
        for(int i = left + 1;i < 26;i++){
            if(range[i][0] < r){
                r = Math.max(r,range[i][1]);
            }else{
                result.add(r - l + 1);
                l = range[i][0];
                r = range[i][1];
            }
        }
        result.add(r - l + 1);
        return result;
    }
}