代码随想录算法训练营第31天—贪心算法05 | ● 435. 无重叠区间 ● *763.划分字母区间 ● *56. 合并区间

435. 无重叠区间

https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

• 考点
  • 贪心算法
  • 重叠区间
• 我的思路
  • 先按照区间左坐标进行排序，方便后续处理
  • 进行for循环，循环范围是0到倒数第二个元素
  • 如果当前区间和下一区间重叠，结果计数加1，同时令下一区间的右坐标等于两个区间右坐标中的较小者，这里体现出了贪心的思路，因为取较小者即令区间尽可能小，也就降低了其与其它区间重叠的可能
  • 计数完毕后返回即可
• 视频讲解关键点总结
  • 和我的思路类似
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x: x[0])result = 0for i in range(len(intervals) - 1):if intervals[i + 1][0] < intervals[i][1]:result += 1intervals[i + 1][1] = min(intervals[i][1], intervals[i + 1][1])return result

*763.划分字母区间

https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html

• 考点
  • 本题不是贪心，但思路近似于重叠区间，因此放到这里
  • 如何记录字母最后出现的位置
  • 有了字母最后位置，如何让整个区间的字母均满足要求
• 我的思路
  • 无思路
• 视频讲解关键点总结
  • 本题两个关键点写在了考点里
  • 一，先遍历一遍字符串，记录每个字符出现的最后位置的索引
  • 二，在循环遍历字符串的过程中，用一个变量记录遍历过的字符所对应的索引最大值，当当前索引和最大值吻合时，记录一次结果
• 我的思路的问题
  • 无思路
• 代码书写问题
  • 无
• 可执行代码

class Solution:def partitionLabels(self, s: str) -> List[int]:last_position = [0] * 26for i in range(len(s)):last_position[ord(s[i]) - ord('a')] = iresult = []start_index = 0end_index = 0for i in range(len(s)):end_index = max(end_index, last_position[ord(s[i]) - ord('a')])if i == end_index:result.append(i - start_index + 1)start_index = end_index + 1end_index = 0return result

*56. 合并区间

https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

• 考点
  • 贪心算法
  • 重叠区间
• 我的思路
  • 如果区间有重叠，将区间合并，知道当前区间和下一区间不重叠，将当前区间加入结果
• 视频讲解关键点总结
  • 先将第一个区间加入结果列表中
  • 之后判断原列表的当前区间与结果列表的最后一个区间是否重叠，如果重叠，更新结果列表的最后一个区间
  • 如果不重叠，直接把当前区间加入结果列表
• 我的思路的问题
  • 会遗漏最后一个区间
• 代码书写问题
  • 无
• 可执行代码

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