当前位置：首页 > news >正文

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

news 来源：原创 2024/9/21 17:11:14

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 resintervals.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完结！！！