第三十天|贪心算法| 452. 用最少数量的箭引爆气球，435. 无重叠区间 ，763.划分字母区间

目录

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

435. 无重叠区间

763.划分字母区间

---

今天的题目都算是 重叠区间 问题。

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

为了让气球尽可能的重叠，需要对数组进行排序。

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

    class Solution {
        public int findMinArrowShots(int[][] points) {
//            Arrays.sort(points, (a, b) -> {
//                if (a[0] == b[0]) {
//                    return Integer.compare(a[1], b[1]);
//                }
//                return Integer.compare(a[0], b[0]);
//            });
            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]) {
                    count++;
                } else {
                    points[i][1] = Math.min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
                }
            }
            return count;
        }
    }

• 时间复杂度：O(nlog n)，排序需要 O(NlogN) 的复杂度
• 空间复杂度：O( log n)，java所使用的内置函数用的是快速排序需要 logN 的空间

注意，排序这块需要用 Integer.compare(a[0], b[0])

因为一开始我用的是：

if (a[0] == b[0]) {
    return a[1] - b[1];
}
return a[0] - b[0];

当数组包含极大或极小的整数（如 Integer.MIN_VALUE 和 Integer.MAX_VALUE）时，直接使用减法计算差值可能导致 整数溢出，则会产生溢出错误。

为了避免溢出，可以使用 Integer.compare 方法代替减法，因为它可以安全地比较两个整数而不会产生溢出。Integer.compare(a[0], b[0])：会返回一个负值、零或正值，分别表示 a[0] 小于、等于或大于 b[0]。

435. 无重叠区间

按左边排序，不管右边顺序。相交的时候取最小的右边。

与452很类似，简单。

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

763.划分字母区间

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

• 统计每一个字符最后出现的位置（很妙，这个记录法，详见代码部分）
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

代码部分注意看下面那个简洁部分，注释的部分for循环中有点麻烦。但是思路逻辑什么的都是一样的。

    class Solution {
        public List<Integer> partitionLabels(String s) {
//            int[] str = new int[26];
//            for (int i = 0; i < s.length(); i++) {
//                str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
//            }
//            List<Integer> result = new LinkedList<>();
//            for (int i = 0, start = 0, end = str[s.charAt(0)-'a']; i < s.length(); i++) {
//                if (i == end){
//                    result.add(end-start+1);
//                    if (i == s.length()-1){
//                        break;
//                    }
//                    end = str[s.charAt(i+1)-'a'];
//                    start = i+1;
//                }else {
//                    end = Math.max(end,str[s.charAt(i)-'a']);
//                }
//            }
//            return result;
            
            //简洁版本
            int[] str = new int[27];
            for (int i = 0; i < s.length(); i++) {
                str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
            }
            List<Integer> result = new LinkedList<>();
            for (int i = 0, start = -1, end = 0; i < s.length(); i++) {
                end = Math.max(end,str[s.charAt(i)-'a']);
                if (i == end){
                    result.add(end-start);
                    start = i;
                }
            }
            return result;
        }
    }

第三十天的总算是结束了，直冲Day31！

原文地址：https://blog.csdn.net/qq_51726003/article/details/143661170

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！