音平商城谁做的网站,网站的二级网页关键词,苏州城乡住房建设厅网站,千度网站DAY 33 贪心算法part04
1. 452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points #xff0c;其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可…DAY 33 贪心算法part04
1. 452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 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:# x_start升序 x_end 降序排列# 对于当前的x_end ,如果下一个x_start小于等于它表明有交点直到下一个x_start大于x_end开始新的一轮交点计数points.sort(keylambda x: x[0])cnt 0x_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 1else: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(keylambda x: x[1])cnt 0right float(-inf)print(fintervals {intervals})for interval in intervals:if interval[0] right:right interval[1]cnt 1return len(intervals) - 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 0while i len(s):char s[i]right_index char_int_dict[char][-1]j i 1cnt 1while j right_index:char s[j]right_index max(char_int_dict[char][-1], right_index)j 1cnt 1res.append(cnt)i jreturn res
