435. 無重疊區(qū)間

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

• 考點(diǎn)
  • 貪心算法
  • 重疊區(qū)間
• 我的思路
  • 先按照區(qū)間左坐標(biāo)進(jìn)行排序，方便后續(xù)處理
  • 進(jìn)行for循環(huán)，循環(huán)范圍是0到倒數(shù)第二個元素
  • 如果當(dāng)前區(qū)間和下一區(qū)間重疊，結(jié)果計(jì)數(shù)加1，同時令下一區(qū)間的右坐標(biāo)等于兩個區(qū)間右坐標(biāo)中的較小者，這里體現(xiàn)出了貪心的思路，因?yàn)槿≥^小者即令區(qū)間盡可能小，也就降低了其與其它區(qū)間重疊的可能
  • 計(jì)數(shù)完畢后返回即可
• 視頻講解關(guān)鍵點(diǎn)總結(jié)
  • 和我的思路類似
• 我的思路的問題
  • 無
• 代碼書寫問題
  • 無
• 可執(zhí)行代碼

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.劃分字母區(qū)間

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

• 考點(diǎn)
  • 本題不是貪心，但思路近似于重疊區(qū)間，因此放到這里
  • 如何記錄字母最后出現(xiàn)的位置
  • 有了字母最后位置，如何讓整個區(qū)間的字母均滿足要求
• 我的思路
  • 無思路
• 視頻講解關(guān)鍵點(diǎn)總結(jié)
  • 本題兩個關(guān)鍵點(diǎn)寫在了考點(diǎn)里
  • 一，先遍歷一遍字符串，記錄每個字符出現(xiàn)的最后位置的索引
  • 二，在循環(huán)遍歷字符串的過程中，用一個變量記錄遍歷過的字符所對應(yīng)的索引最大值，當(dāng)當(dāng)前索引和最大值吻合時，記錄一次結(jié)果
• 我的思路的問題
  • 無思路
• 代碼書寫問題
  • 無
• 可執(zhí)行代碼

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. 合并區(qū)間

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

• 考點(diǎn)
  • 貪心算法
  • 重疊區(qū)間
• 我的思路
  • 如果區(qū)間有重疊，將區(qū)間合并，知道當(dāng)前區(qū)間和下一區(qū)間不重疊，將當(dāng)前區(qū)間加入結(jié)果
• 視頻講解關(guān)鍵點(diǎn)總結(jié)
  • 先將第一個區(qū)間加入結(jié)果列表中
  • 之后判斷原列表的當(dāng)前區(qū)間與結(jié)果列表的最后一個區(qū)間是否重疊，如果重疊，更新結(jié)果列表的最后一個區(qū)間
  • 如果不重疊，直接把當(dāng)前區(qū)間加入結(jié)果列表
• 我的思路的問題
  • 會遺漏最后一個區(qū)間
• 代碼書寫問題
  • 無
• 可執(zhí)行代碼

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