刷题笔记Day31贪心算法part05
刷题笔记Day30：贪心算法part04题目：合并区间
56. 合并区间 - 力扣（LeetCode）
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [,,,]
输出：[,,]
解释：区间 和 重叠, 将它们合并为 .思路：本体的思路和昨天的几道题目相同，利用此刻元素的左边界和上一刻元素的右边界进行对比，若右边界大说明有交集，若右边界小说明没有交集；若有交集则判断两个元素的右边界谁大，将大的作为此刻元素的右边界从而方便和下一个元素进行对比。此题用了一个比较巧妙的方式从而避免了在intervals中对元素进行操作，题解中给了一个result数组，若有交集则更新数组最后一个元素的右边界值，若没交际则直接将这个元素push到数组的末尾。同时，比较的对象也从上一个元素变为了和result数组当前的末尾元素。
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
if(a == b) return a < b;
return a < b;
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
vector<vector<int>> result;
result.push_back(intervals);
for(int i = 1 ; i < intervals.size();i++){
if(result.back() >= intervals){
result.back() = max(result.back(),intervals);
}
else{
result.push_back(intervals);
}
}
return result;
}
};题目：单调递增的数字
738. 单调递增的数字 - 力扣（LeetCode）
当且仅当每个相邻位数上的数字 x 和 y 满足 x 0 ;i--){ if(s < s) { s --; flag = i; } } for(int i = flag; i < s.size();i++) { s = '9'; } return stoi(s); }};
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]