435. 无重叠区间
题目
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。
思考
这题其实和射气球题目很像，也是将intervals先按每个元素第二位从小到大排序，然后判断每个元素的第二位是否小于等于后一元素的第一位，如果小于等于，那么证明不重叠，将两个区间合并，如何大于，那么重叠，直接res++
代码
class Solution {
public:
static bool cmp(vector
return a[1] < b[1];
}
int eraseOverlapIntervals(vector
int res = 0;
sort(intervals.begin(), intervals.end(), cmp);
int curStart = intervals[0][1];
int curEnd = intervals[0][1];
for(int i = 1; i < intervals.size(); i++) {
if(curEnd <= intervals[i][0]) {
curEnd = intervals[i][1];
curStart = min(curStart, intervals[i][0]);
continue;
}
else {
res++;
}
}
return res;
}
};
763.划分字母区间
题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
思考
这题非常巧妙，有几个关键点：
1、找到字符串中每个字母的最大inde：，比如示例a的最大index就是8，这个需要用hash数组，先遍历字符串，然后用hash[s[i] - 'a'] = i;的方法来获取
2、用双指针left right，right，遍历字符串时right在持续更新right = max(right, hash[s[i] - 'a']);因为取的是最大区间，那么得找到这里区间里的最大index
3、当i == 最大index即right时，进行收割，然后left要等于i+1
代码
class Solution {
public:
vector
int hash[27] = {0};
for(int i = 0; i < s.size(); i++) {
hash[s[i] - 'a'] = i;
}
vector
int left = 0;
int right = 0;
for(int i = 0; i < s.size(); i++) {
right = max(right, hash[s[i] - 'a']);
if(i == right) {
res.push_back(right - left + 1);
left = i+1;
}
}
return res;
}
};
56. 合并区间
题目
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
思考
这题其实和无重叠区间思路一样，都是将intervals排序，唯一需要注意的是这里需要按照每个元素的第一位大小进行排序，因为如果排第二位的话会非常麻烦，然后思路还是和无重叠区间一样就行
代码
class Solution {
public:
static bool cmp(vector
return a[0] < b[0];
}
vector
sort(intervals.begin(), intervals.end(), cmp);
vector
res.push_back(intervals[0]);
for(int i = 1; i < intervals.size(); i++) {
if(res.back()[1] < intervals[i][0]) {
res.push_back(intervals[i]);
}
else {
res.back()[1] = max(res.back()[1], intervals[i][1]);
}
}
return res;
}
};
参考阅读
发表评论