贪心算法的第四篇博客，主要是重叠问题的练习，思路都较为简单，最后一题可能需要着重思考一下
452. 用最少数量的箭引爆气球
遍历数组，如果存在重叠则减少一支箭（不重叠则增加一支箭）
重叠的判定：基于累积的最小重叠区间
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) == 0: return 0points.sort(key=lambda x: x[0]) # 默认升序result = 1for i in range(1, len(points)):if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=result += 1 else:points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界return result435. 无重叠区间
注：图片引用自《代码随想录》
右排序，遍历左端点，小于则删除（左排序相同思路）
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if not intervals:return 0intervals.sort(key=lambda 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 += 1return count763.划分字母区间
贪心思路：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
注：图片引用自《代码随想录》
class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {} # 存储每个字符最后出现的位置for i, ch in enumerate(s): # 遍历可迭代对象, 生成索引和值last_occurrence[ch] = i # 重点理解写法result = []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按照上面两题思路仿写
class Solution:def countLabels(self, s):# 初始化一个长度为26的区间列表，初始值为负无穷hash = [[float('-inf'), float('-inf')] for _ in range(26)]hash_filter = []for i in range(len(s)):if hash[ord(s[i]) - ord('a')][0] == float('-inf'):hash[ord(s[i]) - ord('a')][0] = ihash[ord(s[i]) - ord('a')][1] = i # 记录每一个元素的起始位置和结束位置for i in range(len(hash)):if hash[i][0] != float('-inf'):hash_filter.append(hash[i]) # 按照字母顺序拼接, 刨除空元素return hash_filterdef partitionLabels(self, s):res = []hash = self.countLabels(s)hash.sort(key=lambda x: x[0]) # 按左边界从小到大排序rightBoard = hash[0][1] # 记录最大右边界leftBoard = 0for i in range(1, len(hash)):if hash[i][0] > rightBoard: # 出现分割点(出现新元素左边界大于现存的最大右边界)res.append(rightBoard - leftBoard + 1)leftBoard = hash[i][0]rightBoard = max(rightBoard, hash[i][1]) # 最大右边界res.append(rightBoard - leftBoard + 1) # 最右端return res
)
