当前位置：首页 > article >正文

【代码随想录|贪心算法重叠区间问题】

article 2025/1/16 14:41:35

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

题目链接452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

这道题是要求从下往上穿箭，把所有气球扎爆要的最少箭的数量

思路就是我们比较这个气球和上一个气球有没有重合的，重合我们一根箭一起就射了，不重合我们就要单独拿根箭射它，每个气球都有左边界points[i][0]，和右边界points[i][1]，我当前气球左边界都大于上一个气球的右边界，那就一点不挨边，箭加一，如果不是那就肯定挨着了，一根箭就够用（箭就不用加一），但是为了判断后面还有没有气球跟他俩连着，我直接更新气球的右边界来和后面的进行比较，以防我后面的气球万一也可以跟这俩一起射爆。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0)
            return 0;
        int result = 1;
        sort(points.begin(), points.end(), cmp);
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) {//不挨边
                result++;//需要箭
            } else {//挨着的，不用箭了
                points[i][1] = min(points[i][1], points[i - 1][1]);//更新右边界和后面进行比较
            }
        }
        return result;
    }
};

435.无重叠区间

题目链接：435. 无重叠区间 - 力扣（LeetCode）

这道题感觉跟上一道题很相像，因为这道题是要去掉重叠区间，让剩下的区间都不重叠，思路就是我们进行先按左区间从小到大进行遍历，如果遍历到重叠的区间我们就要去掉一个重叠区间，所以定义的count++，为了判断后面还有没有区间跟他俩重合，我直接更新区间的右边界来和后面的进行比较。如果遍历到不重叠的区间，就啥也不用做，写代码只重合的区间就行。

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;
        int count = 0;
        sort(intervals.begin(), intervals.end(), cmp);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {//如果重叠
                count++;
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);//更新右区间
            }
        }
        return count;
    }
};

763.划分字母区间

题目链接：763. 划分字母区间 - 力扣（LeetCode）

这道题问的是怎么把同一字母分到一个片段

思路是要分两步走：1、就是要先定义一个数组里面存放着每个字母的最远边界，2、然后我遍历这个字符串，遍历到哪个字母我就去找相应字母的最远边界，如果我们遍历到了现存的最远边界了那就收集结果，继续遍历。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};
        for (int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a'] = i;//每个字符出现的最后位置
        }
        vector<int> result;
        int right = 0;
        int left = 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 = right + 1;//继续遍历
            }
        }
        return result;
    }
};

最开始就一直不明白hash数组是怎么存放最远边界的，我觉得字母不一样的话hash数组不是东一个西一个的吗，然后手动遍历了大概懂了。

假设有字符串S = "abacabad"

当 i = 0, S[0] = 'a':
- hash['a' - 'a'] = hash[0] = 0
- 更新后的 hash: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 1, S[1] = 'b':
- hash['b' - 'a'] = hash[1] = 1
- 更新后的 hash: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 2, S[2] = 'a':
- hash['a' - 'a'] = hash[0] = 2
- 更新后的 hash: [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 3, S[3] = 'c':
- hash['c' - 'a'] = hash[2] = 3
- 更新后的 hash: [2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 4, S[4] = 'a':
- hash['a' - 'a'] = hash[0] = 4
- 更新后的 hash: [4, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 5, S[5] = 'b':
- hash['b' - 'a'] = hash[1] = 5
- 更新后的 hash: [4, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 6, S[6] = 'a':
- hash['a' - 'a'] = hash[0] = 6
- 更新后的 hash: [6, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
当 i = 7, S[7] = 'd':
- hash['d' - 'a'] = hash[3] = 7
- 更新后的 hash: [6, 5, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]