做ppt哪些网站的图片质量高,北京手机建站模板,企业网站建设公司电话成都,网站 关键字435. 无重叠区间
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。
解题思路#xff1a;
本题重点在于求重叠区间#xff0c;将所有区间按照左边界从小到大排序。从第二个区… 435. 无重叠区间
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
解题思路
本题重点在于求重叠区间将所有区间按照左边界从小到大排序。从第二个区间开始与上一个区间进行比较如果当前区间左边界小于上一区间右边界说明区间重叠并将两区间有边界定义为较小的有边界用来和下一区间进行比较。
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:if not intervals:return 0#排序intervals.sort(key lambda x: (x[0],x[1]))result 0for i in range(1, len(intervals)):if intervals[i-1][1]intervals[i][0]:#区间重叠result 1intervals[i][1] min(intervals[i-1][1], intervals[i][1])return result763.划分字母区间 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 解题思路 要想得到最大区间需要先遍历整个s记录每个字母的最大index例如用hash_table记录。设置startend记录每个字符片段的起始并在第二次遍历的时候更新end当iend时说明遍历到了当前字符片段的终点添加进result并更新start。 class Solution:def partitionLabels(self, s: str) - List[int]:hash_table {}for i , j in enumerate(s):hash_table[j] i#get the farest index for each letterresult []start 0end 0for i,j in enumerate(s):end max(end, hash_table[j])#update the end idx to the farestif i end:#meet the last idx of this intervalresult.append(end-start1)start i1return result 56. 合并区间 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 解题思路 本题重点在于发现重叠区间时直接在result中进行删改而不是在interval中更新避免后续在result中更改长度。先在result中添加进第一个区间剩下逻辑与leetcode435类似如果发现左区间小于上一个右区间在result中更改最后一个的右区间否则在result中添加当前区间。 class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort(key lambda x:x[0])result []if len(intervals)1:result.append(intervals[0])return resultresult.append(intervals[0])for i in range(1, len(intervals)):if intervals[i][0]result[-1][1]:#有重叠直接在result中更新# intervals[i][0] min(intervals[i-1][0], intervals[i][0])result[-1][1] max(result[-1][1], intervals[i][1])else:#添加当前区间result.append(intervals[i])return result
