门户网站营销特点,快抖霸屏乐云seo,内蒙古网站建设流程,加快网站访问速度435.无重叠区间 思路#xff1a;找到删除几个区间#xff0c;让题目给出的区间没有重叠部分#xff0c;那么首先我们先进行排序#xff08;按照左边界排序#xff09;#xff0c;那么下一个区间的左边界小于上一个区间的右边界#xff0c;那么这两个区间一定有重叠的部分…435.无重叠区间 思路找到删除几个区间让题目给出的区间没有重叠部分那么首先我们先进行排序按照左边界排序那么下一个区间的左边界小于上一个区间的右边界那么这两个区间一定有重叠的部分说明这两个区间必须要移除掉一个那么这两个移除掉哪一个呢应该移除掉两个区间中右边界更大的那一个这样才能最大限度避免对于下一个区间左边界与这两个区间重复那么如果没有重复那么就不更新什么 时间复杂度O(nlogn) 空间复杂度O(n) sort()中涉及到一个快排的问题 class Solution {
public:int result0;static bool cmp(vectorint a,vectorint b){return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end());for(int i1;iintervals.size();i){if(intervals[i][0]intervals[i-1][1]){result;intervals[i][1]min(intervals[i-1][1],intervals[i][1]);}}return result;}
};763.划分字母区间 思路这道题没啥思路看了答案学习一下先用一个数组记录一下有点类似于哈希表的做法记录一下每个字母在该数组中最远的位置然后再去遍历遍历到最远的地方此处就是分割点 时间复杂度O(n) 空间复杂度O(1) class Solution {
public:vectorint partitionLabels(string s) {int hash[27]{0};for(int i0;is.size();i){hash[s[i]-a]i;}vectorint result;int left0;int right0;for(int i0;is.size();i){rightmax(right,hash[s[i]-a]);if(iright){result.push_back(right-left1);lefti1;}}return result;}
};56.合并区间 思路最开始的时候思路也是先进行排序然后判断两个区间是否重叠将区间更新成更大的一个区间但是对于怎么加入到result中出现问题了如果不先将第一个加入区间利用第一个去判断那么在后面会出现仅有一个的无法加入区间这里没想到 时间复杂度O(nlogn) 空间复杂度O(logn) class Solution {
public:static bool cmp(vectorint a,vectorint b){return a[0]b[0];}vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(),intervals.end(),cmp);vectorvectorint result;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;}
};总结 重叠区间的问题一般都是将其先排序然后判断上一个区间的右边值与下一个区间的左边值是否重叠等问题
