代码随想录算法训练营第三十天 | 贪心算法 part04
452. 用最少数量的箭引爆气球
本题的关键是首先根据左边界或右边界进行排序，使得可能重叠的气球排在一起，好处理。
class Solution {static bool cmp(vector<int>& a, vector<int>& b) {if (a[0] == b[0])return a[1] < b[1];elsereturn a[0] < b[0];}
public:int findMinArrowShots(vector<vector<int>>& points) {int result = 0;sort(points.begin(), points.end(), cmp);for (int i = 0; i < points.size(); ++i) {result++;int end = points[i][1];while (i < points.size() - 1 && end >= points[i + 1][0]) {end = min(end, points[i + 1][1]);i++;}}return result;}
};
435. 无重叠区间
与上一题很相似，关键是在发生重叠后要更新end，新的右边界，因为肯定要去掉一个数组，贪心的做法是去掉右边界大的。
class Solution {static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0])return a[1] < b[1];else return a[0] < b[0];}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int result = 0;for (int i = 1; i < intervals.size(); ++i) {int end = intervals[i - 1][1];while (i < intervals.size() && end > intervals[i][0]) {end = min(end, intervals[i][1]);result++;i++;}}return result;}
};
763.划分字母区间
本题分两步：
- 通过遍历字符串s，找到每个字符出现的最后位置。
- 根据上述信息，再遍历一遍字符串s，开始分割。
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 start = 0, end = 0;for (int i = 0; i < s.size(); ++i) {end = max(end, hash[s[i] - 'a']);if (i == end) {result.push_back(end - start + 1);start = end + 1;}}return result;}
};