ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀,每一条都经过真实交付验证。

算法第三十天--贪心算法part04(第八章)

2026/8/4 5:45:25 拓冰建站 浏览量
算法第三十天--贪心算法part04(第八章)

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

452. 用最少数量的箭引爆气球 - 力扣(LeetCode)

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:#第一个气球 [1,6],我们在 6 射第一箭#第二个 [2,8],起点是 2 ≤ 6,能打 ✅if not points:return 0points.sort(key=lambda x: x[1])result = 1end = points[0][1]for i in range(1, len(points)):if points[i][0] > end:result += 1end = points[i][1]return result

 2.无重叠区间

435. 无重叠区间 - 力扣(LeetCode)

3.划分字母区间

763. 划分字母区间 - 力扣(LeetCode)

 

class Solution:def partitionLabels(self, s: str) -> List[int]:#同一字母最多出现在一个片段中last_occurrence = {}for i, ch in enumerate(s):#第一步:记录每个字母最后一次出现的位置last_occurrence[ch] = ires = []start = 0end = 0for i, ch in enumerate(s):end = max(end, last_occurrence[ch])if i == end:res.append(end-start+1)start = i+1return res

今天有点难加油!晚上继续!