「代码随想录算法训练营」第二十六天 | 贪心算法 part4
452. 用最少数量的箭引爆气球
题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
题目难度：中等
文章讲解：https://programmercarl.com/0452.用最少数量的箭引爆气球.html
视频讲解：https://www.bilibili.com/video/BV1SA41167xe
题目状态：有点思路，但是没通过，靠ChatGPT通过
思路：
首先看一下题目的大致意思，如下图：
首先要通过气球的终点来进行排序，然后初始化箭的个数为1，因为至少会有一支箭，之后判断下一个气球的开头位置是否小于前一个气球的结尾，若大于，则箭的个数要加1，直到遍历结束。
代码：
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
// Sort the points based on the end position of the balloons
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int res = 1; // At least one arrow is needed
int end = points[0][1];
for (int i = 1; i < points.size(); i++) {
// If the current balloon starts after the end of the previous balloon
if (points[i][0] > end) {
res++;
end = points[i][1];
}
}
return res;
}
};
435. 无重叠区间
题目链接：https://leetcode.cn/problems/non-overlapping-intervals/
题目难度：中等
文章讲解：https://programmercarl.com/0435.无重叠区间.html
视频讲解：https://www.bilibili.com/video/BV1A14y1c7E1
题目状态：看题解
思路：
首先根据每个区间的末尾位置来排序，若末尾的位置比下一个区间的开头要小，则说明这两个区间没有重叠，记录一下无重叠区间的个数，然后继续遍历，直到遍历结束，返回有重叠的个数。
代码：
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. 划分字母区间
题目链接：https://leetcode.cn/problems/partition-labels/
题目难度：中等
文章讲解：https://programmercarl.com/0763.划分字母区间.html
视频讲解：https://www.bilibili.com/video/BV18G4y1K7d5
题目状态：看题解
思路：
记录每一个字符的最远出现位置，然后定义一个区间，遍历在该区间中的字符最远出现的位置，若最后遍历到的位置正好为其区间中所含字符的最远位置，说明找到了该区间，更新下一个区间的开头为当前区间的下一个位置，继续遍历。
代码：
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;
}
};