网站建设 风险说明书,固原建设厅官方网站,网页设计接单网站,网站建设 镇江435.无重叠区间
题目链接
讲解链接
本题思路与前一道类似#xff0c;代码只需稍作修改。当后一个区间左边界小于前一个区间右边界时说明这两个区间存在重叠部分#xff0c;此时将count 1#xff0c;并更新右边界为二者中较小的值即可。
class Solution:def eraseOverla…435.无重叠区间
题目链接
讲解链接
本题思路与前一道类似代码只需稍作修改。当后一个区间左边界小于前一个区间右边界时说明这两个区间存在重叠部分此时将count 1并更新右边界为二者中较小的值即可。
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:intervals.sort(keylambda x: x[0]) # 按照区间左边界排序count 0 # 记录重叠区间数量for i in range(1, len(intervals)):if intervals[i][0] intervals[i - 1][1]: # 若当前区间左边界小于前一个区间的右边界则说明这两个区间重叠intervals[i][1] min(intervals[i - 1][1], intervals[i][1]) # 更新右边界取两个区间右边界的最小值count 1 # 重叠数1return count763.划分字母区间
题目链接
讲解链接
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
class Solution:def partitionLabels(self, s: str) - List[int]:last_occurrence {}for i, ch in enumerate(s):last_occurrence[ch] iresult []start 0end 0for i, ch in enumerate(s):end max(end, last_occurrence[ch])if i end:result.append(end - start 1)start i 1return result
56.合并区间
题目链接
讲解链接
本题与之前的无重叠区间和射气球类似其实就是合并区间后将得到的左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:if len(intervals) 1: # 若数组长度为1则直接返回return intervalsintervals.sort(keylambda x:x[0]) # 按照左边界进行排序result [] # 保存结果left, right intervals[0][0], intervals[0][1] # 初始化左右边界for i in range(len(intervals)):if intervals[i][0] right and intervals[i][1] right: # 如果当前区间与左右边界有重叠部分right intervals[i][1] # 更新右边界elif intervals[i][0] right: # 如果当前区间与左右边界无重叠部分result.append([left, right]) # 将之前的边界加入结果集left intervals[i][0] # 更新左边界right intervals[i][1] # 更新右边界result.append([left, right]) # 将最后一个结果添加到结果中return result
