代码随想录算法训练营第30天 | 第八章 贪心算法05
文章目录
- 今日记录
- 56.合并区间
- 738.单调递增的数字
- 总结
今日记录
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 (result.back()[1] >= intervals[i][0]) {result.back()[1] = max(result.back()[1], intervals[i][1]);} else {result.push_back(intervals[i]);}}return result;}
};
738.单调递增的数字
Leetcode链接
易错点：
- 应该是从后向前遍历；
- 有多位都不是单增时，从后往前遍历导致最开始遍历的应该都变成9而不止其中一位；
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始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);}
};