【Day27】LeetCode：56. 合并区间，738. 单调递增的数字

文章目录LeetCode56. 合并区间思路解答LeetCode738. 单调递增的数字思路解答LeetCode56. 合并区间https://leetcode.cn/problems/merge-intervals/思路按区间左端点升序排序intervals。用区间[last_start, last_end]记录上一个正在合并的区间。然后遍历数组1如果当前区间和正在合并的区间重叠如果完全重叠就直接跳过如果没有完全重叠则更新正在合并的区间为[last_start, end]。2如果当前区间和正在的合并的区间不重叠则说明上一个正在合并的区间可以合并结束将合并后的区间加入结果然后将当前区间作为正在合并的区间。最后将最后一个正在合并的区间添加进结果。解答classSolution:defmerge(self,intervals:List[List[int]])-List[List[int]]:nlen(intervals)intervals.sort(keylambdax:x[0])# 按区间左端点升序排序results[]last_startintervals[0][0]last_endintervals[0][1]forindex,intervalinenumerate(intervals[1:]):startinterval[0]endinterval[1]ifstartlast_endandendlast_end:# 重叠且不完全覆盖last_endendelifstartlast_end:# 完全不重叠插入上一个results.append([last_start,last_end])last_startstart last_endend results.append([last_start,last_end])# 插入最后一个returnresultsLeetCode738. 单调递增的数字https://leetcode.cn/problems/monotone-increasing-digits/description/思路倒序遍历数组如果nums[i-1] nums[i]即出现递减则标记flag i使得其后所有数都为9然后nums[i-1]--。例如出现324因为3 2所以标记数字 2 前一位 - 1得到299。解答classSolution:defmonotoneIncreasingDigits(self,n:int)-int:numslist(str(n))flaglen(nums)# 标记从哪一位开始后面都是9foriinrange(len(nums)-1,0,-1):# 倒序遍历ifnums[i-1]nums[i]:flagi nums[i-1]str(int(nums[i-1])-1)foriinrange(flag,len(nums)):nums[i]9returnint(.join(nums))