代码随想录算法训练营第36天（py）| 贪心 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间

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

力扣链接
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数。

思路

当气球出现重叠，一起射，所用弓箭最少。为了让气球尽可能的重叠，需要对数组进行排序。把气球排序之后，从前到后遍历气球，被射过的气球跳过即可。
在这里插入图片描述
如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points)==0:
            return 0

        points.sort(key = lambda x:x[0])#按照左边界排序

        res = 1
        for i in range(len(points)):
            if points[i][0] > points[i-1][1]: # 如果不重合
                res += 1
            else: # 如果重合
                points[i][1] = min(points[i - 1][1], points[i][1]); # 更新重叠气球最小右边界
        return res

435. 无重叠区间

力扣链接
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。(区间可以“接触”，但不能“重叠”）

思路

按照左边界排序，统计重叠区间数量即可

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals)==0:
            return 0
        intervals.sort(key = lambda x:x[0])#按照左边界排序
        cnt = 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]) #更新重叠区间
                cnt += 1
        return cnt

763.划分字母区间

力扣链接
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

思路

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：

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

在这里插入图片描述


class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_appear = {} #哈希表记录字符最后出现的位置
        for index, char in enumerate(s):
            last_appear[char] = index

        res = []
        start = 0
        end = 0
        for index, char in enumerate(s):
            end = max(last_appear[char], end)
            if index == end:
                #res.append(s[start:end+1])
                res.append(end - start + 1)
                start = end + 1
        return res