day36
435.无重叠区间
题目链接:435. 无重叠区间
和射气球那个题的思路一样,按照左边界进行排序,然后按照射气球那道题过即可
class Solution {
public:
static bool cmp(vector<int>& a, 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;
for( int i = 1; i < intervals.size(); i++){
if( intervals[i][0] < intervals[i-1][1]){
result++;
intervals[i][1] = min(intervals[i][1],intervals[i-1][1]);
}
}
return result;
}
};
763.划分字母区间
题目链接:763. 划分字母区间
分两步:
- 统计每一个字符最后出现的位置
- 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
// 时间:O(n)
// 空间:O(1)
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;
}
//定义每个数组的左右边界
int left = 0;
int right = 0;
vector<int> result;
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;
}
};
56.合并区间
题目链接:56. 合并区间
思路和之前一样,重点关注合并时候的操作,result.back()表示取最后一个元素
class Solution {
public:
static bool cmp(vector<int>& a, 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;
sort( intervals.begin(),intervals.end(),cmp);
vector<vector<int>> result;
result.push_back(intervals[0]);
for( int i = 1; i < intervals.size(); i++){
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;
}
};