福州网站制作套餐,更改网站名字,杭州 网站开发公司,邢台城乡建设局网站#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 无重叠区间划分字母区间合并… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 无重叠区间划分字母区间合并区间总结 今天的三道题都是重叠区间的题也是代码简单但思路难想其中第二题不太算贪心但是也能贪心写出来但是这里不给贪心代码因为挺难写的。
无重叠区间
435. 无重叠区间 - 力扣LeetCode
这道题是让我们返回要删除几个区间才能达到该数组内部不再出现重叠区间了其实并不需要进行真正的删除区间模拟因为我们只需要返回要删除区间的个数并不是要真的在数组里直接删除。
应该按照左边界排序还是右边界排序呢其实理论上来说都是可行的但是左边界排序不好理解我们采用对右边界从小到大排序然后正向的遍历数组。由于我们排完序将右边界小的值排在了前面所以我们可以按照先找非重叠的部分有几个然后用总数减去非重叠就得到了我们要删除几个区间直接求要删除的重叠区间个数是十分困难的。
我们排完序的第一个区间一定是右区间最小的我们以它开始寻找一个区间满足左区间大于或等于它这时再按照新找到的区间的右区间接着去找下一个区间每找到一个新区间自增计数器。
class Solution {
public:static bool cmp(const vectorinta,const vectorintb){return a[1]b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {if(intervals.size()0){return 0;}sort(intervals.begin(),intervals.end(),cmp);int count1;int endintervals[0][1];for(int i1;iintervals.size();i){if(endintervals[i][0]){endintervals[i][1];count;}}return intervals.size()-count;}
};再强调一下是按照右区间大小排的序所以不用担心即使有左边界小右边界很大的区间它也不会被先遍历到。
划分字母区间
763. 划分字母区间 - 力扣LeetCode
划分字母区间更像是回溯算法里的切割字符串的问题实际上我认为这种方法应该貌似也是可行的。但是在这里我们要介绍的不是那种回溯递归的方法而是用一个标记数组标记每一个不同的字母最远出现在哪一个位置做完了标记数组之后我们再进行对字符串的分割。
要注意分割后的每一块区域重新组合应该还是能得到原来字符串所以不能选用会影响字符串顺序的算法。
我们定义两个变量left和rightleft存的是当前要分割区间的最左端下标right是最右端用循环遍历该字母区间如果碰到了当前字母在标记数组中的值比现在的right大那么更新right值。直到变量i与right值相等我们进行相减1压入返回数组中加1是因为我们求得是划分的区间有个字母。
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; for (int i 0; i S.size(); i) { hash[S[i] - a] i;}vectorint 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;}
};标记数组这个做题思路还是很巧妙的让right存储最大值相当于实时的更新分割线所处的地方i和right相等时说明了当前分割线以内都是可以被分割的后面不会出现相同字母因为标记数组标记了这些字母最远出现在哪里。在分割完毕的时候我们再更新left的值。
合并区间
56. 合并区间 - 力扣LeetCode
合并区间我觉得和无重叠区间差不多都是让数组内不出现重叠区间。只不过这个合并区间是真的要返回合并后的区间。思路其实我觉得能做出第一道题或许会有做出这道题的可能。
思路是先排序但是和上一个不一样的是这道题要从左区间从小到大排序好做一点因为它的思路是直接合并重叠部分区间而区别于第一道题的我们是找出非重叠的区间个数那道题我们是避免找到重叠的而这道题我们按照左区间从小到大的好处是左区间小的会排在一起这样我们比较时候发现第二个区间如果它的左区间小于前一个的右区间则说明两区间一定有某一部分发生重叠将其合并后将合并区间看做整体扩大其右边界范围直到找不出下一个的左区间小于上一个右区间为止将改后区间加入数组然后全部遍历后返回。
class Solution {
public:
static bool cmp(vectorinta,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(result.back()[1]intervals[i][0]){result.back()[1]max(result.back()[1],intervals[i][1]);}else result.push_back(intervals[i]);}return result;}
};这是代码实现的缩减部分主要就是比较区间然后不断改变右区间的值实现了区间的合并也并不是真正的删除重叠的区间然后扩充。这里的else的目的是如果当前判断到的区间不符合重叠了那直接加入到数组里然后用这个新加入的区间再重复之前的比较往复便能实现所谓合并区间。
总结
今天我们完成了无重叠区间、划分字母区间、合并区间三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
