56.合并区间
题目链接56. 合并区间 - 力扣(LeetCode)
这道题思路跟前两道也很像,就是更新把相同的区间合并而已。
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);result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= intervals[i - 1][1]) {result.back()[1] = max(intervals[i][1], result.back()[1]);} else {result.push_back(intervals[i]);}}return result;}
};
738.单调递增的数字
题目链接: 738. 单调递增的数字 - 力扣(LeetCode)
我滴妈,这道题的思路好牛啊
我觉得大概的思路就是先把这个数字转成字符串,好对每个数进行变化,
思路就是把从后往前遍历,前面的数比现在的数大的话就把前面的数-1,让后面这个数有选择大的数(9)的可能
但是如果直接把前一位-1后一位设置成9,如果传入的数是1000的话,结果就会变成0900,所以我设置一个flag来记录当前数要设置为9的地方,后面统一都设置为9了,因为我只要这个数为9,后面的数肯定都是9(没有比9更大的数了)
然后最后把字符串转成数值型返回答案
那为什么不从前往后进行修改?
因为从前往后进行修改的话,我后面的数修改了会把一个数-1,会影响已经遍历的的数的大小关系,从后往前遍历的话,我就可以一边遍历一边用修改后的结果
class Solution {
public:int monotoneIncreasingDigits(int n) {string result=to_string(n);int flag=result.size();//满足条件的话就不设9,所以初始赋值为整个数的大小for(int i=result.size()-1;i>0;i--){if(result[i-1]>result[i]){result[i-1]=result[i-1]-1;//前面的数-1flag=i;//这个数和后面的都准备设置为9}}for(int i=flag;i<=result.size()-1;i++){result[i]='9';//遍历到整个数的末尾}return stoi(result);}
};