本文主要是介绍DAY36: 贪心算法part5区间问题435、763、56，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode: 435 无重叠区间
和昨天学习的到的打气球的题目属于一样的框架和题型。
基本思路：首先将区间按照左区间从小到大进行排序，判断前面的元素右区间和后面的元素左区间是否重叠，如果重叠了需要统计重叠区间的数量，同时更新区间，选择保留右区间元素较小的那个，防止多次删除的问题。代码如下：
时间复杂度O(nlogn)
空间复杂度O(N)
class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {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++){if(intervals[i][0] < intervals[i - 1][1]){//如果区间重叠了intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);//保留右区间较小的那个result++;}}return result;}
};当然这道题还有其他的做法，比如使用左区间排序来减去不重叠的区间，
代码随想录
Leetcode: 763 划分字母区间
基本思路是寻找到遍历过的所有字母的最远编解来划分。
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
class Solution {
public:vector<int> partitionLabels(string s) {int count[27] = {0};//因为只有26个字母，所以开一个27的数组来记录每个字母的最远下标for(int i = 0; i < s.size(); i++){count[s[i] - 'a'] = i;//记录最远下标}vector<int> result;int end = 0;//记录上一个划分的分割点int countmax = 0;//记录当前遍历中的最远的字母下标for(int i = 0; i < s.size(); i++){countmax = max(countmax, count[s[i] - 'a']);//更新最远下标if(i == countmax){result.push_back(i - end + 1);//输入结果end = i + 1;//更新结束的分割点}}return result;}
};Leetcode: 56 合并区间
本质上还是和第一题判断区间的思路差不多，只需要判断一下是不是区间重合，如果区间重合就合并，更新结果。
class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];
}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if(intervals[i][0] <= result.back()[1]){result.back()[1] = max(result.back()[1], intervals[i][1]); //更新结果区间}else{result.push_back(intervals[i]); // 区间不重叠}}return result;}
};以前的写法
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ans;for (int i = 0; i < intervals.size();) {int t = intervals[i][1];int j = i + 1;while (j < intervals.size() && intervals[j][0] <= t) {t = max(t, intervals[j][1]);j++;}ans.push_back({ intervals[i][0], t });i = j;}return ans;}
};这篇关于DAY36: 贪心算法part5区间问题435、763、56的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
