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

代码随想录算法训练营day30

article 2025/1/17 6:05:38

代码随想录算法训练营

—day30

文章目录

代码随想录算法训练营
前言
一、452. 用最少数量的箭引爆气球
二、435. 无重叠区间
三、763.划分字母区间
总结

前言

今天是算法营的第30天，希望自己能够坚持下来！
今日主要是贪心算法的重叠区域问题：
● 452. 用最少数量的箭引爆气球
● 435. 无重叠区间
● 763.划分字母区间

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

题目链接
文章讲解
视频讲解

在这里插入图片描述

思路：
1.先按左区间排序
2.遍历区间，从第二个元素开始判断，当前元素的左区间是否比上一个元素的右区间大
3.是则说明需要多一支箭
4.否则更新当前的右区间，取上一个右区间和当前右区间最小值

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;
        sort(points.begin(), points.end(), cmp); //按左区间排序

        int result = 1; //只有一个元素时也要用一支箭
        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. 无重叠区间

题目链接
文章讲解
视频讲解

在这里插入图片描述

思路：

对区间按左边界排序
判断当前区间的左边界是否比前一个区间的右边界小
是则证明有有重叠，需要删除，将区间最大的删掉，更新当前区间的右边界（取最小值）

代码如下：

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 = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= intervals[i-1][1]) continue; //不重叠
            else {
                result++; //相当于删除了一个区间，因为要删除最小数量，删除右边界最大的区间，留下边界范围小的区间
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]); //更新当前的右边界
            }
        }

        return result;
    }
};

三、763.划分字母区间

题目链接
文章讲解
视频讲解

在这里插入图片描述

思路：
1.先用一个哈希数组存放每个字母的最远下标
2.遍历字符串，用left记录边界左边，right记录边界右边
3.遍历过程中一直更新right，取当前字母最远下标跟当前right的最大值
3.当遍历到i=right时，说明已经找到一个区间，存下left和right。继续从right+1开始找
（字符串s[i] - ‘a’ 可以让字母从0开始作为hash数组的索引）
代码如下：

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; //更新字母的最远坐标，'a'-'a' = 0
        }

        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;
    }
};