《代码随想录》刷题打卡day27：贪心算法part05

文章目录【56.合并区间】【738.单调递增的数字】总结【56.合并区间】思路和前些题相同比较简答。第一个区间就可以放进结果集里后面如果重叠在result上直接合并简化操作。class Solution { public: static bool cmp(const vectorint a, vectorint b){ return a[0] b[0]; } vectorvectorint result; vectorvectorint merge(vectorvectorint intervals) { if(intervals.size() 0) return result; sort(intervals.begin(), intervals.end(), cmp); // 第一个区间就可以放进结果集里后面如果重叠在result上直接合并 result.push_back(intervals[0]); for(int i 1; i intervals.size(); i){ if(result.back()[1] intervals[i][0]){ // 发现重叠区间 // 合并区间只更新右边界就好因为result.back()的左边界一定是最小值因为我们按照左边界排序的 result.back()[1] max(result.back()[1], intervals[i][1]); }else{ result.push_back(intervals[i]); } } return result; } };【738.单调递增的数字】思路例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]–然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。从后向前遍历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); } };总结