day30 第八章 贪心算法 part04
452. 用最少数量的箭引爆气球
先排序，再算重叠区间
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if len(points)==0:
return 0
points.sort(key=lambda x:x[0])
result = 1
for i in range(1, len(points)):
if points[i][0] > points[i-1][1]:
result += 1
else:
points[i][1] = min(points[i][1], points[i-1][1])
return result
435. 无重叠区间
跟上一题一样
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# if len(intervals)==0:
# return 0
intervals.sort(key = lambda x:x[0])
result = 0
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
continue
else:
result += 1
intervals[i][1] = min(intervals[i][1], intervals[i-1][1])
return result
763.划分字母区间
先准备一下每个字母的最大位置，以便后续继续计算。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
# 求得字母的最远位置
alphebet_dict = dict()
for i in range(len(s)):
alphebet_dict[s[i]] = i
# 遍历，求得每一个片段内能容纳多少字母
end = 0
start = 0
result = []
for i in range(len(s)):
end = max(end, alphebet_dict[s[i]])
if end == i:
result.append(end-start+1)
start = i+1
return result原文地址：https://blog.csdn.net/mvufi/article/details/147224585
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！