今天的三道题都是区间问题
435. 无重叠区间
讲解链接:https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
思路分析在代码注释
class Solution {
public:
static bool cmp(const vector<int>&a, const vector<int>& b) {
if(a[0]==b[0])
return a[1]<b[1];
return a[0]<b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int result = 0;
//和上一篇中的思想一样,需要一个变量来存储目前这个区间的右边界
//初始为第一个区间的右边界
int right_bound = intervals[0][1];
//还是从第二个元素开始(若只有一个元素也没关系)
for(int i=1;i<intervals.size();i++) {
//合理的情况:(无交集)第二个区间的左边界 要大于等于第一个区间的右边界
if(intervals[i][0] >= right_bound) {
//更新右边界
right_bound = intervals[i][1];
}
else {
result++;
//这里也需要对边界进行一个更新;
right_bound = min(right_bound,intervals[i][1]);
continue;
}
}
return result;
}
};
763.划分字母区间
讲解链接:https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
思路:
可以分为如下两步:
统计每一个字符最后出现的位置
从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
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;
}
vector<int> 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) {
//记录集合中的元素个数:利用right-left+1
result.push_back(right-left+1);
//同时更新下一个左界
left = i+1;
}
}
return result;
}
};
56. 合并区间
讲解链接:https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
新学了一招
result.back()[1] 表示 result 向量中最后一个区间的结束时间。result.back() 返回 result 向量中的最后一个元素,这是一个区间(向量)。然后 [1] 表示这个区间的结束时间。以下是一个详细解释:
result.back() 返回 result 的最后一个元素,它是一个 vector,代表一个区间。
result.back()[1] 返回这个区间的第二个元素,即区间的结束时间
class Solution {
public:
static bool cmp(const vector<int>&a, const vector<int>& b){
if(a[0]==b[0])
return a[1]<b[1];
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<=1)
return intervals;
vector<vector<int>> result;
sort(intervals.begin(),intervals.end(),cmp);
//初始化这个左界
//不可以这样赋值 : result[k][0] = intervals[0][0];
result.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++) {
//新学了一招
//.back()是最后一个向量,.back()[0]左边界,[1]右边界
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;
}
};