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