做挂广告网站,洋气的文化传媒公司名字,python开发wordpress,网站开发备案认证435. 无重叠区间 这道题和前一天的射箭题目思想类似#xff0c;用总区间个数-不重叠的区间个数等于需要去除的区间个数。首先对左边界排序#xff0c;如果当前的左边界大于等于上一区间的右边界#xff0c;则说明是一个不重叠的区间#xff0c;否则#xff0c;更新上一重… 435. 无重叠区间 这道题和前一天的射箭题目思想类似用总区间个数-不重叠的区间个数等于需要去除的区间个数。首先对左边界排序如果当前的左边界大于等于上一区间的右边界则说明是一个不重叠的区间否则更新上一重叠区间的最小右边界详细代码如下 class Solution {
public:static bool cmp(vectorinta, vectorintb){return a[0]b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {//类似射箭if(intervals.size()1) return 0;sort(intervals.begin(),intervals.end(),cmp);int sum 1;for(int i1;iintervals.size();i){if(intervals[i][0]intervals[i-1][1]){sum;}else{intervals[i][1] min(intervals[i][1],intervals[i-1][1]);}}return intervals.size()-sum;}
}; 763.划分字母区间 这道题的思路很巧妙首先记录每个字符最后出现的位置然后从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点如图 详细代码如下 class Solution {
public:vectorint partitionLabels(string s) {int hash[27] {0};for(int i0;is.size();i) //记录最后出现的位置{hash[s[i]-a] i;}vectorint res;int right0;int left 0;for(int i 0;is.size();i){right max(right,hash[s[i]-a]);if(iright){res.push_back(right-left1);lefti1;}}return res;}
}; 56. 合并区间 这道题目和之前的重叠区间思路相似也是先左边界排序然后再判断是否重叠不重叠直接添加元素重叠的话则需要更新右边界左边界一定是最小的无需更新详细代码如下 class Solution {
public:static bool cmp(vectorinta, vectorintb){return a[0]b[0];}vectorvectorint merge(vectorvectorint intervals) {if(intervals.size()1) return intervals;sort(intervals.begin(),intervals.end(),cmp);vectorvectorint res;res.push_back(intervals[0]); //先加入元素for(int i 1;iintervals.size();i){if(intervals[i][0]res.back()[1]) //不重叠{res.push_back(intervals[i]); //不重叠直接添加元素}else //重叠{//更新右边界左一定最小res.back()[1] max(res.back()[1], intervals[i][1]); }}return res;}
};
