网站自动弹窗代码,国外哪些网站可以兼职做任务,只做旧房翻新的装修公司,自有服务器可以做网站吗第八章 贪心算法 part05
1.LeetCode. 无重叠区间
1.1题目链接#xff1a;435. 无重叠区间
文章讲解#xff1a;代码随想录 视频讲解#xff1a;B站卡哥视频
1.2思路#xff1a;我来按照右边界排序#xff0c;从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区…第八章 贪心算法 part05
1.LeetCode. 无重叠区间
1.1题目链接435. 无重叠区间
文章讲解代码随想录 视频讲解B站卡哥视频
1.2思路我来按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的如图 区间123456都按照右边界排好序。
当确定区间 1 和 区间2 重叠后如何确定是否与 区间3 也重贴呢
就是取 区间1 和 区间2 右边界的最小值因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分如果这个最小值也触达到区间3那么说明 区间 123都是重合的。
接下来就是找大于区间1结束位置的区间是从区间4开始。那有同学问了为什么不从区间5开始别忘了已经是按照右边界排序的了。
区间4结束之后再找到区间6所以一共记录非交叉区间的个数是三个。
总共区间个数为6减去非交叉区间的个数3。移除区间的最小数量就是3。
1.3附加代码如下所示
//该题目和之前的射箭气球问题很相似
class Solution {
public:static bool cmp(const vectorinta,const vectorintb){return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {if(intervals.size()0)return 0;int result0;sort(intervals.begin(),intervals.end(),cmp);for(int i1;iintervals.size();i)//如果当前区间左边界大于前一个区间的有边界就不需要进行移除区间操作{if(intervals[i][0]intervals[i-1][1]){continue;}else//当前{intervals[i][1]min(intervals[i][1],intervals[i-1][1]);result;}}return result;}
};2.LeetCode.划分字母区间
2.1题目链接763.划分字母区间
文章讲解代码随想录 视频讲解B站卡哥视频
2.2思路在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置 从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点如图 2.3附加代码如下所示
class Solution {
public:vectorint partitionLabels(string s) {vectorintreuslt;int hash[27]{0};for(int i0;is.size();i){hash[s[i]-a]i;//统计字母最远距离的下标}int left0;//字符分割的左边界int right0;//字符分割的右边界for(int ileft;is.size();i){rightmax(right,hash[s[i]-a]);if(righti)//找到字母最远距离的下标与实际位置对应上了就分割{reuslt.push_back(right-left1);leftright1;//更新下一次进行分割的起始点}}return reuslt;}
};3.LeetCode.合并区间
3.1题目链接[56. 合并区间(https://leetcode.cn/problems/merge-intervals/)
文章讲解代码随想录 视频讲解B站卡哥视频
3.2思路大家如果认真做题的话话发现和我们刚刚讲过的452. 用最少数量的箭引爆气球 )和 435. 无重叠区间都是一个套路。
这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。
所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。
按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是
这么说有点抽象看图注意图中区间都是按照左边界排序之后了 知道如何判断重复之后剩下的就是合并了如何去模拟合并区间呢
其实就是用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
3.3附加代码如下所示
//精简版
class Solution {
public:static bool cmp(const vectorinta,const vectorintb){return a[0]b[0];}vectorvectorint merge(vectorvectorint intervals) {vectorvectorintresult;if(intervals.size()0)return result;sort(intervals.begin(),intervals.end(),cmp);//按照左边界大小进行排序result.push_back(intervals[0]);//先加入第一个集合区间for(int i1;iintervals.size();i){if(intervals[i][0]result.back()[1])//前后两个集合没有重叠时候,要和加入result中的进行比较而不是原数组中的{result.push_back(intervals[i]);}else //前后两个集合有重叠时候且后一个右边界大于前一个右边界{result.back()[1]max(result.back()[1],intervals[i][1]);//左边界是不变的选择前后两个右边界大的那一个}}return result;}
};
