????????貪心算法的第四篇博客，主要是重疊問題的練習，思路都較為簡單，最后一題可能需要著重思考一下
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
)
