题目引用
- 合并区间
- 单调递增的数字
1. 合并区间
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
学习了昨天的题目之后大家应该对这种题目驾轻就熟了,唯一可能有问题的就是语法上的小细节,大家看看代码注意一下就好啦。
class Solution {
public:static bool cmp(vector<int>& a,vector<int>& b){return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;if(intervals.size()==0) return res;sort(intervals.begin(),intervals.end(),cmp);res.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(res.back()[1]>=intervals[i][0]){res.back()[1]=max(res.back()[1],intervals[i][1]);}else{res.push_back(intervals[i]);}}return res;}
};
2. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
这道题像不像咱们小学做的数学拓展呀,题目理解上大家应该没什么问题,那么我们来看一下怎么做。
首先大家肯定能想到当前一位大于后一位时我们让其–,再从后往前赋值为9。
但是是从后往前判断–呢还是从前往后判断–呢,我们来模拟一下,以332举例,当我们从前往后这样执行时,会发现我们的结果最后会是329,不符合题意,所以应该是从后往前遍历比较。
这里的局部最优就是尽量让当前数字符合递增规律,全局最优就是让数字整体符合递增规律而且为最大。
那么我们直接看代码吧:
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);}
};
总结
到这里咱们的贪心就算结束啦,希望大家下来好好吸收和总结。