您现在的位置是：首页 >学无止境 >代码随想录算法训练营第三十三天| 贪心算法05网站首页学无止境

56. 合并区间

本题也是重叠区间问题，如果昨天三道都吸收的话，本题就容易理解了。

代码随想录

可以自己写出来，注意点：

1. 按左边界排序

2. 找到重叠区间，修改intervals

3. 放入结果的时候注意最后一组元素

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

738. 单调递增的数字

代码随想录

稍微有点绕，注意点：

1. 数字转成列表形式，便于对每一位进行操作

2. 从右向左遍历，若当前位比前一位小，那么前一位数字应该减1，当前位及后面的每一位均为9则为最大数

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n_list=list(str(n))
        for i in range(len(n_list)-1,0,-1):
            if n_list[i]<n_list[i-1]:
                n_list[i-1]=str(int(n_list[i-1])-1)
                for j in range(i,len(n_list)):
                    n_list[j]='9'        

        return int(''.join(n_list))