代码随想录算法训练营day36|435. 无重叠区间、763.划分字母区间、56. 合并区间

435. 无重叠区间 

代���随想录

class Solution:    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:        intervals.sort(key=lambda x:x[0])        result = 0        for i in range(1,len(intervals)):            if intervals[i][0]                
763.划分字母区间 
     
代码随想录
     
分为如下两步：
     

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

  如图：

  class Solution:    def partitionLabels(self, s: str) -> List[int]:        #统计每个字母出现的最后位置        last_occurrence = {}        for i,ch in enumerate(s):            last_occurrence[ch] = i                result = []        start = 0         end = 0        for i,ch in enumerate(s):            end = max(end,last_occurrence[ch])            if i == end :                result.append(end-start+1)                start = i+1                return result

   enumerate用法：

  对一个列表，既要遍历索引又要遍历元素时可以使用enumerate函数：

  list1 = ["这", "是", "一个", "测试"]for index, item in enumerate(list1):    print(index,item)

   enumerate还可以接收第二个参数，用于指定索引起始值

  list1 = ["这", "是", "一个", "测试"]for index, item in enumerate(list1,1):    print(index,item)

   56. 合并区间  

  代码随想录

  class Solution:    def merge(self, intervals: List[List[int]]) -> List[List[int]]:        intervals.sort(key = lambda x:x[0])        result = []        for i in range(1,len(intervals)):            if intervals[i][0] > intervals[i-1][1]:                result.append(intervals[i-1])            else:                intervals[i][0] = intervals[i-1][0]                intervals[i][1] = max(intervals[i-1][1],intervals[i][1])                        if i == len(intervals)-1:                result.append(intervals[i])                    return result

  或者先把第一个元素添加进result，接着进行比较

  class Solution:    def merge(self, intervals):        result = []        if len(intervals) == 0:            return result  # 区间集合为空直接返回        intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序        result.append(intervals[0])  # 第一个区间可以直接放入结果集中        for i in range(1, len(intervals)):            if result[-1][1] >= intervals[i][0]:  # 发现重叠区间                # 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的                result[-1][1] = max(result[-1][1], intervals[i][1])            else:                result.append(intervals[i])  # 区间不重叠        return result