DAY30|贪心算法Part04|LeetCode:452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间

目录

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

基本思路

C++代码

LeetCode:435. 无重叠区间

基本思路

C++代码

LeetCode:763.划分字母区间

基本思路

C++代码

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

力扣代码链接

文字讲解：LeetCode:452. 用最少数量的箭引爆气球

视频讲解：贪心算法，判断重叠区间问题

基本思路

        首先我们应该先对气球进行排序，这样才能保证让气球尽可能重叠，因为只有重叠的时候我们才能用更少的箭去射爆气球。那么按照气球起始位置排序，还是按照气球终止位置排序呢？

        其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

        从前向后遍历遇到重叠的气球了怎么办？如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。以例一为例：

        可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。

C++代码

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);

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

        这里points[i][1] = min(points[i - 1][1], points[i][1]); 是为了更新重叠气球的最小右边界，这样的话对于下一次循环过程中，第i+1个气球如果和更新边界后的第i个气球不存在重叠区域，那么就不存在一支箭射爆三个气球的情况。

LeetCode:435. 无重叠区间

力扣代码链接

文字讲解：LeetCode:435. 无重叠区间

视频讲解：贪心算法，依然是判断重叠区间

基本思路

        这个题目和上一题有些相似，都是需要判断区间是否重叠，此时应该按照左边界进行排序还是右边界进行排序呢？其实都可以。主要就是为了让区间尽可能的重叠。

        按照左边界进行排序，我们依旧按照从前向后进行遍历，如果遍历到当前区间的起始位置大于上一个区间的终止位置就说明存在重叠区间，即进行记录。

        另外我们还需要对两个区间的终止位置进行比较，取最小值并赋给变量end，end就是区间分割点，这样当和下个区间相比较时，就可以判断三个区间是否存在公共区间，并且用count用来记录重叠区间的个数。

C++代码

class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 改为左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 注意这里从0开始，因为是记录重叠区间
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {   
            if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况
            else { // 重叠情况 
                end = min(end, intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};

LeetCode:763.划分字母区间

力扣代码链接

文字讲解：LeetCode:763.划分字母区间

视频讲解：贪心算法，寻找最远的出现位置！

基本思路

        题目要求同一字母最多出现在一个片段中，难点在于如何把同一个字母的都圈在同一个区间里呢？在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

        可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

C++代码

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};