代码随想录算法训练营day31 | 56. 合并区间、738.单调递增的数字

碎碎念：加油
参考：代码随想录

56. 合并区间

题目链接

56. 合并区间

思想

这道题的核心还是判断重叠区间，本题和之前做过的452. 用最少数量的箭引爆气球、435. 无重叠区间的区别在于判断出重叠区间之后的操作，本题需要做的是合并重叠区间。
首先要让重叠的区间尽可能挨在一起，那么就要对区间排序，本解法用的是对左边界排序。
遍历所有区间，如果当前遍历到的区间的左边界小于等于上一个区间的右边界，那么就发生了重叠，需要继续合并区间的操作，具体做法是修改区间的右边界；如果当前遍历到的区间的左边界大于上一个区间的右边界，没有发生重叠，把上一个区间加入result即可。

题解

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;if (intervals.size() == 0) return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= result.back()[1]) {result.back()[1] = max(intervals[i][1], result.back()[1]);} else {result.push_back(intervals[i]);}}return result;} 
};

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:result = []if len(intervals) == 0:return resultintervals.sort(key=lambda x:x[0])result.append(intervals[0])for i in range(1, len(intervals)):if result[-1][1] >= intervals[i][0]:result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])return result

反思

不建议像之前一些题的做法一样在原数组上修改，防止遍历的时候混乱。

738.单调递增的数字

题目链接

738.单调递增的数字

思想

遍历数字的每一位，如果发现两位不符合要求，要对前一位减一，后一位要取最大的9。应该从后往前遍历，否则得到的可能不符合题意。
定义了一个flag，表示某一位往后都是9。

题解

class Solution {
public:int monotoneIncreasingDigits(int n) {string str = to_string(n);int flag = str.size(); for (int i = str.size() - 1; i > 0; i--) {if (str[i - 1] > str[i]) {str[i - 1]--;flag = i;}}for (int i = flag; i < str.size(); i++) {str[i] = '9';}return stoi(str);}
};

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:strNum = str(n)flag = len(strNum)for i in range(len(strNum) - 1, 0, -1):if strNum[i - 1] > strNum[i]:flag = istrNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' +strNum[i+1:]return int(strNum)

反思

传入的是int类型的，为了方便遍历把它转换为string类型的。
注意关于flag的处理，为什么设置这样的初始值。