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

碎碎念：加油
参考：代码随想录
56. 归并区间

题目链接

56. 归并区间
思想

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

1. class Solution {
2. public:
3.     static bool cmp (const vector<int>& a, const vector<int>& b){
4.         return a[0] < b[0];
5.     }
6.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
7.         vector<vector<int>> result;
8.         if (intervals.size() == 0) return result;
9.         sort(intervals.begin(), intervals.end(), cmp);
10.         result.push_back(intervals[0]);
11.         for (int i = 1; i < intervals.size(); i++) {
12.             if (intervals[i][0] <= result.back()[1]) {
13.                 result.back()[1] = max(intervals[i][1], result.back()[1]);
14.             } else {
15.                 result.push_back(intervals[i]);
16.             }
17.         }
18.         return result;
19.     }
20. };

复制代码

1. class Solution:
2.     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3.         result = []
4.         if len(intervals) == 0:
5.             return result
6.         intervals.sort(key=lambda x:x[0])
7.         result.append(intervals[0])
9.         for i in range(1, len(intervals)):
10.             if result[-1][1] >= intervals[i][0]:
11.                 result[-1][1] = max(result[-1][1], intervals[i][1])
12.             else:
13.                 result.append(intervals[i])
14.         
15.         return result

复制代码

反思

不建议像之前一些题的做法一样在原数组上修改，防止遍历的时间混乱。
738.单调递增的数字

题目链接

738.单调递增的数字
思想

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

1. class Solution {
2. public:
3.     int monotoneIncreasingDigits(int n) {
4.         string str = to_string(n);
5.         int flag = str.size();
6.         for (int i = str.size() - 1; i > 0; i--) {
7.             if (str[i - 1] > str[i]) {
8.                 str[i - 1]--;
9.                 flag = i;
10.             }
11.         }
12.         for (int i = flag; i < str.size(); i++) {
13.             str[i] = '9';
14.         }
15.         return stoi(str);
16.     }
17. };

复制代码

1. class Solution:
2.     def monotoneIncreasingDigits(self, n: int) -> int:
3.         strNum = str(n)
4.         flag = len(strNum)
6.         for i in range(len(strNum) - 1, 0, -1):
7.             if strNum[i - 1] > strNum[i]:
8.                 flag = i
9.                 strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]
10.             
11.         for i in range(flag, len(strNum)):
12.             strNum = strNum[:i] + '9' +strNum[i+1:]
13.         
14.         return int(strNum)

复制代码

反思

传入的是int类型的，为了方便遍历把它转换为string类型的。
留意关于flag的处置惩罚，为什么设置如许的初始值。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。