算法训练营day30 贪心算法④ 重叠问题 452. 用最少数量的箭引爆气球、435. 无重叠区间 、 763.划分字母区间

        贪心算法的第四篇博客，主要是重叠问题的练习，思路都较为简单，最后一题可能需要着重思考一下

452. 用最少数量的箭引爆气球

        遍历数组，如果存在重叠则减少一支箭（不重叠则增加一支箭）

        重叠的判定：基于累积的最小重叠区间

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0: return 0
        points.sort(key=lambda x: x[0]) # 默认升序
        
        result = 1
        for 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 result

435. 无重叠区间 

注：图片引用自《代码随想录》

        右排序，遍历左端点，小于则删除（左排序相同思路）

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.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 += 1
        
        return count

763.划分字母区间

贪心思路：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

注：图片引用自《代码随想录》

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}  # 存储每个字符最后出现的位置
        for i, ch in enumerate(s): # 遍历可迭代对象, 生成索引和值
            last_occurrence[ch] = i # 重点理解写法

        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置
            if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间
                result.append(end - start + 1)
                start = i + 1

        return 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] = i
            hash[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_filter

    def partitionLabels(self, s):
        res = []
        hash = self.countLabels(s)
        hash.sort(key=lambda x: x[0])  # 按左边界从小到大排序
        rightBoard = hash[0][1]  # 记录最大右边界
        leftBoard = 0
        for 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