代码随想录27期|Python|Day37|56.合并区间|738.单调递增的数字

56. 合并区间

 简单题，需要判断上一个区间右边界和下一个区间左边界的大小关系，并作合并。步骤如下：

1、对区间按照区间左端点进行排序，从小到大；

2、将第一个区间保存在res内，并循环判断res内最后一个区间的右端点和左端点的大小关系；

3、如果大于，则取两个区间右端点较大者为合并后的区间右端点；如果小于，则说明区间没有重合，直接放入res即可。

注意：每次从res中取出的是最后一个区间（索引为-1），不是循环interval对应的i-1（考虑一个从头合并到尾的区间，res中实际上就这一个大区间）。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        if len(intervals) == 0:
            return res
        intervals.sort(key=lambda x: x[0])

        res.append(intervals[0])

        for i in range(1, len(intervals)):
            if res[-1][1] >= intervals[i][0]:  ## 注意这里是res的最后一个，不是i-1个，注意不能和interval的i对齐
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])
        return res

738. 单调递增的数字

本题不难，想通一个事实是关键：

一个数字，当不满足后一位大于等于前一位的时候，最大值是多少？

答案是前一位-1，后一位变成9（因为9是最大的数字）。

比如，322变成319再变成299，可以注意到每次操作的都是两位，所以可以使用贪心方法。步骤如下：

1、从后往前比较是关键，因为需要保证最后一位是最大的（最大就是9）；

2、比较两位大小，如果不满足递增，前一位-1，后一位变成9；

进一步说，出现过不满足情况的数字，其输出都满足前一位-1，后面不管几位全是9。

为了方便操作，将int转化为str类型（由于ASCII码在数字字符上是连续的，所以可以直接比较大小）。则上述过程的第二步实际上为：

取出前一位前面的切片，前一位-1，后面几位全部为9。最后拼接在一起。

class Solution(object):
    def monotoneIncreasingDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        numstr = str(n)

        for i in range(len(numstr)-1, 0 ,-1):
            if numstr[i] < numstr[i-1]:
                numstr = numstr[:i-1] + str(int(numstr[i-1])-1) + '9' * (len(numstr)-i)
        return int(numstr)

Day37完结！！！