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

第30天，贪心part04，加油，编程语言：C++

目录

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

435.无重叠区间 

763.划分字母区间 

总结 

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

文档讲解：代码随想录用最少数量的箭引爆气球

视频讲解：手撕用最少数量的箭引爆气球

题目：

学习：根据题干，很直观的贪心逻辑就是尽可能一箭射掉多的区间重叠的气球，最后得到最少数量的箭。因此本题的关键在于求解合适的重叠区间。

本题不需要模拟气球射爆把元素移除的过程，因为本题只需要计算最小的射箭数，因此我们只需要使用一个整型变量result，来手机合适出箭的重叠区间即可。

显然为了让气球尽可能的重叠，我们可以先对数组进行排序。按照起始位置或者按照终止位置排序都行，这里我们假设按照起始位置进行排序，以示例1为例：

排序后，我们可以看到，如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。这里一定要注意一定是右边边界的最小值，因为我们在遍历过程中，会发现气球3的起始点是在气球2的区间内的，但是依照上图显然我们是不能同时射爆气球1,2,3的，因此我们更新右边界的逻辑一定要注意是更新最小值。

代码：

//时间复杂度O(nlogn)快速排序的复杂度
//空间复杂度O(1)
class Solution {
public:
    static bool camp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 1) return 1;
        //对数组points咱找起始坐标从小到大进行排序
        sort(points.begin(), points.end(), camp);
        //贪心逻辑尽可能找重合的气球射
        int end = points[0][1]; //初始化，记录第一个气球的右边界
        int result = 1; //默认第一个气球要射出一根
        for(int i = 1; i < points.size(); i++) {
            if(points[i][0] <= end) {
                if(points[i][1] < end) {
                    end = points[i][1]; //更新右边界，取重合最小的，这样才能保证射重复的气球
                }
            }
            else {
                result++;
                end = points[i][1];
            }
        }
        return result;    
    }
};

435.无重叠区间 

文档讲解：代码随想录无重叠区间

视频讲解：手撕无重叠区间

题目：

学习：本题实际上和上题是差不多的，甚至可以说是一样的。本题也是需要找重叠的区间。对于上一题来说射箭的数量，其实就是非重叠区间的数量，因此将区间总数减去射箭的数量，就是需要移除区间的数量。（但要注意，两道题的边界条件是不同的，对于本题来说区间相邻是不算重叠的，但是上题区间相邻是算重叠的，因此需要变一下边界条件）

代码：注意本题直接使用intervals[i][1]代替end变量

//时间复杂度O(nlogn)
//空间复杂度O(1)
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 result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= intervals[i - 1][1]) {
                result++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
            }
        }
        return intervals.size() - result;
    }
};

当然本题也可以正向去记录要删除的区间，这里我们采用按终点排序的方式，同样要注意分割点是 重合的最小右边界。

代码：

//时间复杂度O(nlogn)
//空间复杂度O(1)实际是O(n)，因为快排存在递归调用，需要开辟栈区间
class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

763.划分字母区间 

文档讲解：代码随想录划分字母区间

视频讲解：手撕划分字母区间

题目：

学习： 本题同样也需要划分空间，但我认为本题比上面两题更难，因为本题不能够排序，也没有什么划分规律，因此难以下手。

本题的关键在于需要从全局的角度去划分数组，是无法通过一次遍历就把区间找出的。依据本题的要求，我们在遍历过程中，不仅要关注当前遍历的字母，还需要关注字符串后面有没有该字母，并且遍历的过程中还在不断的加入新的字母，因此一次遍历是得不到答案的。

但是我们也可以发现，如果我们知道了每个字母最后出现的位置，实际上本题就能够很容易解出来了，就是在遍历过程中，如果找到了之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。也即后面的字母肯定不存在于前面的字符串中。因此本题我们可以使用两个for循环，分为两步解决本题：

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

代码：根据以上步骤，便可写出代码。

注意：当我们需要记录元素对应的下标时，我们很容易想到使用哈希表，但哈希表的种类有很多，我们解题的过程中，一定要从简单到复杂（数组->set->map）去思考使用哪种哈希表。对于本题来说我们可以采用map结构来保存元素和其对应的下标，但显然本题明确了字符串s仅由小写字母构成，元素数量有限，并且元素之间是具备连续关系的，因此本题使用数组来作为哈希表是更方便，更简单的。

//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[26] = {0}; //使用数组作为哈希表
        vector<int> result; //记录答案

        //第一个循环，统计每一个字符最后出现的位置
        for(int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a'] = i; //不断更新每个字母对应的最远下标
        }
        int left = 0; //左边界
        int right = 0; //右边界
        //第二个循环，找到分割点
        for(int i = 0; i < s.size(); i++) {
            right = max(right, hash[s[i] - 'a']); //不断更新最远右边界
            if(i == right) { //当i等于right的时候，就说明此时遍历的位置，就是前面所有字母的最远右边界，该位置就是一个分割点
                result.push_back(right - left + 1);
                left = i + 1; //计算下一个分割点
            }
        }
        return result;
    }
};

总结 

上述题目都属于是重叠区间类问题，这类问题贪心逻辑主要在于如何找到合适的重叠区间，每道题根据要求都有不同的模拟方法，因此需要多加练习。