DAY 33 贪心算法part04
1. 452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 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:
# x_start升序， x_end 降序排列
# 对于当前的x_end ,如果下一个x_start小于等于它，表明有交点，直到下一个x_start大于x_end，开始新的一轮交点计数
points.sort(key=lambda x: x[0])
cnt = 0
x_start = float('-inf')
x_end = float('-inf')
for point in points:
if point[0] > x_end:
x_start = point[0]
x_end = point[1]
cnt += 1
else:
x_end = min(x_end, point[1])
return cnt
2. 435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 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[1])
# cnt = 0
# right = float('-inf')
# print(f"intervals {intervals}")
# for interval in intervals:
# if interval[0] >= right:
# right = interval[1]
# cnt += 1
# return len(intervals) - cnt
# 也可以左边界排序，直接计算重叠区间的数量（需要移除的区间数量）
intervals.sort(key=lambda x: x[0])
cnt = 0
#从0开始计算重叠区间，注意这里边界点重合不算重叠
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] >= end:
end = intervals[i][1]
else:
cnt += 1
end = min(end, intervals[i][1])
return cnt
3. 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]:
#首先同一字母只能出现在一个片段中，那么片段结尾一定包含片段开头对应字母最大索引的右边，因此我们可以第一次遍历使用字典存储每个
#字母的索引列表
char_int_dict = dict()
for index, char in enumerate(s):
if char not in char_int_dict:
char_int_dict[char] = [index]
else:
char_int_dict[char].append(index)
res = []
i = 0
while i < len(s):
char = s[i]
right_index = char_int_dict[char][-1]
j = i + 1
cnt = 1
while j <= right_index:
char = s[j]
right_index = max(char_int_dict[char][-1], right_index)
j += 1
cnt += 1
res.append(cnt)
i = j
return res