本文介绍: 一旦包含了某个字母,就不得不向后遍历,使得该字母只出现在这个区间里,寻找所有的该字母,最终将该片段分割,就是寻找该区间里所有字母的最远边界,这个边界就是分割点。还是先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以,我还是按照左边界进行排序,然后考虑重叠的区间,移除数组中的元素,使得区间互不重叠,保证移除的元素数量最少,数组中至少包含一个元素。合并数组中的重叠区间,返回一个不重叠的区间数组,这个数组覆盖输入的所有区间。局部最优,使得重叠区间的个数最大,全局最优,移除最少的元素。
题目1:435 无重叠区间
题目链接:无重叠区间
对题目的理解
移除数组中的元素,使得区间互不重叠,保证移除的元素数量最少,数组中至少包含一个元素
贪心算法
本题和昨天引爆气球的题目相似,还是对数组进行排序(按照左边界排序和右边界排序均可),这里还是选择的左边界排序
代码的精华所在
伪代码
完整代码
class Solution {
public:
static bool cmp(const vector<int>& a, 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 count=0;
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]<intervals[i-1][1]){
count++;
//更新当前重叠区间的最小右边界
intervals[i][1] = min(intervals[i][1],intervals[i-1][1]);
}
}
return count;
}
};
题目2:763 划分字母区间
题目链接:划分字母区间
对题目的理解
由小写字母构成的字符串划分为尽可能多的片段,每个字母最多再一个片段中出现,比如,字母a在第一个片段中出现了,那么a就不能在之后的片段中出现了,注意划分的结果顺序拼接仍为原字符串,最终返回每个片段的长度
一旦包含了某个字母,就不得不向后遍历,使得该字母只出现在这个区间里,寻找所有的该字母,最终将该片段分割,就是寻找该区间里所有字母的最远边界,这个边界就是分割点。
可以分为如下两步:
伪代码
完整代码
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;//求解字符串中每个字母出现的最远下标
}
int left=0,right = 0;//定义片段的左下标,右下标,计算片段的长度
vector<int> result;
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;
}
};
题目3:56 合并区间
题目链接:合并区间
对题目的理解
合并数组中的重叠区间,返回一个不重叠的区间数组,这个数组覆盖输入的所有区间
本题的本质其实还是判断重叠区间问题。
还是先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以,我还是按照左边界进行排序,然后考虑重叠的区间,更新右边界的最大值,对于不重叠的区间,直接存放到result数组中
伪代码
class Solution {
public:
static bool cmp(const vector<int>& a, vector<int>& b){
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> result ;
result.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]<=result.back()[1]){//重叠
//左边界不用更新,因为左边界是按照从小到大排的
//只更新右边界
result.back()[1] = max(intervals[i][1],result.back()[1]);
}
else{//没有重叠
result.push_back(intervals[i]);
}
}
return result;
}
};
原文地址:https://blog.csdn.net/qq_43773652/article/details/134583701
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_6803.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。