刷题笔记Day31贪心算法part05

刷题笔记Day30：贪心算法part04

题目：合并区间

56. 合并区间 - 力扣（LeetCode）
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：

1. 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
2. 输出：[[1,6],[8,10],[15,18]]
3. 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

复制代码

思路：本体的思路和昨天的几道题目相同，利用此刻元素的左边界和上一刻元素的右边界进行对比，若右边界大说明有交集，若右边界小说明没有交集；若有交集则判断两个元素的右边界谁大，将大的作为此刻元素的右边界从而方便和下一个元素进行对比。此题用了一个比较巧妙的方式从而避免了在intervals中对元素进行操作，题解中给了一个result数组，若有交集则更新数组最后一个元素的右边界值，若没交际则直接将这个元素push到数组的末尾。同时，比较的对象也从上一个元素变为了和result数组当前的末尾元素。

1. class Solution {
2. public:
3.     static bool cmp(const vector<int>& a,const vector<int>& b){
4.         if(a[0] == b[0])    return a[1] < b[1];
5.         return a[0] < b[0];
6.     }
7.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
8.         sort(intervals.begin(),intervals.end(),cmp);
9.         vector<vector<int>> result;
10.         result.push_back(intervals[0]);
11.         for(int i = 1 ; i < intervals.size();i++){
12.             if(result.back()[1] >= intervals[i][0]){
13.                 result.back()[1] = max(result.back()[1],intervals[i][1]);
14.             }
15.             else{
16.                 result.push_back(intervals[i]);
17.             }
18.         }
19.         return result;
20.         
21.     }
22. };

复制代码

题目：单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

当且仅当每个相邻位数上的数字 x 和 y 满足 x 0 ;i--){            if(s < s[i-1])            {                s[i-1] --;                flag = i;            }        }        for(int i = flag; i < s.size();i++)        {            s = '9';        }        return stoi(s);    }};[/code]
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！