本文主要是介绍代码随想录算法训练营day31 | 贪心算法 | 56. 合并区间、738.单调递增的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 56. 合并区间
- 思路
- 738.单调递增的数字
- 思路
- 贪心算法专题总结
今天是贪心算法专题的第5天，是贪心算法专题的最后一天
56. 合并区间
建议：本题也是重叠区间问题，如果昨天三道都吸收的话，本题就容易理解了
题目链接：56. 合并区间 - 力扣（LeetCode）
思路
左边界排序数组，记录重叠区间的起始位置start 和 终止位置end。
- 如果end >= intervals[i] [0]，则说明intervals[i]在当前的重叠区间内，更新end = max(end, intervals[i][1]);
- 否则，intervals[i]不在当前的重叠区间内，将当前重叠区间合并，即result.push_back({start, end})，然后更新start 和 end
代码实现：
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b){return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;sort(intervals.begin(), intervals.end(), cmp);int end = intervals[0][1];int start = intervals[0][0];for(int i=0; i<intervals.size(); ++i){if(end >= intervals[i][0]){end = max(end, intervals[i][1]);}else{result.push_back({start, end});start = intervals[i][0];end = intervals[i][1];}}result.push_back({start, end}); // 不要忘了合并最后一个重叠区间return result;}
};
738.单调递增的数字
题目链接：738. 单调递增的数字 - 力扣（LeetCode）
思路
首先将数字转化为字符串strNum，方便后续处理。本题只需要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了
这样，我们从后向前遍历，重复利用上次比较得出的结果，找到最后一处strNum[i - 1] > strNum[i]的位置i，用flag记录这个位置i，从flag到末尾都赋值为9，strNum就是最终结果
以332为例，332->329->299，flag=1，从下标1到最后，将所有的位置都赋值9
代码如下：
class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for(int i=strNum.size()-1; i>0; --i){if(strNum[i-1] > strNum[i]){flag = i; strNum[i-1]--;}}for(int i=flag; i<strNum.size(); ++i){strNum[i] = '9';}return stoi(strNum);}
};
贪心算法专题总结
可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了
代码随想录 (programmercarl.com)
这篇关于代码随想录算法训练营day31 | 贪心算法 | 56. 合并区间、738.单调递增的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
