这是基于代码随想录的每日打卡
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
贪心
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key=lambda x:x[0])x1=points[0][0] # 初始时左边界x2=points[0][1] # 初始时右边界res=0 #记录结果for point in points:# 下一个气球左边界大于上一个气球右边界，直接记录结果且更新边界if point[0]>x2: res+=1x1=point[0]x2=point[1]else:# 如果左边界在原边界中，说明可以和前面的气球一起射# 则更新左边界为新气球的左边界，右边界为原来边界和新边界的最小值，才能保证气球一起射x1=point[0]x2=min(x2,point[1])res+=1return res# 注：更新x1也可以不写，因为判断逻辑只关系到x2,这里主要是对边界更直观
运行结果
435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
贪心
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x:x[0])right=intervals[0][1] # 初始化右边界res=0 # 记录结果for i in range(1,len(intervals)):# 如果下一个区间的左边界大于前一个区间右边界，则更新新右边界if intervals[i][0]>=right:right=intervals[i][1]# 如果下一个区间的左边界小于前一个区间右边界，则说明发生重叠# 更新右边界，取最小值是因为尽可能地取区间小的，区间大的有可能会与后面更多区间重叠，体现贪心else:res+=1right=min(right,intervals[i][1])return res
运行结果
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
贪心
class Solution:def partitionLabels(self, s: str) -> List[int]:# 统计每个字母的最远出现位置from collections import defaultdicthash_table=defaultdict(int)for i in range(len(s)):hash_table[s[i]]=icur=0 # 当前遍历字母下标res=[] # 存放结果far=0 # 记录当前字符串中字符的最远下标while cur<len(s):# 更新当前区间的最远下标if hash_table[s[cur]]>far:far=hash_table[s[cur]]# 如果已经遍历到最远下标了，则收割结果if cur==far:res.append(cur+1-sum(res))# 更新指针cur+=1return res
运行结果
