Posted on 2023-04-03 16:27
Uriel 阅读(33)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
游标.移动窗口 、
排序
给出每个人的体重people[i]和小船的载客量limit,每次最多搭载两个人,问最少要几艘船可以运送完所有人,保证人的最大体重不超过载客量
贪心,先对people排序,然后两个游标从左到右,若两者相加超过载客量,则这艘船只搭载右指针重的那个人,右指针向中间移动,否则搭载这两个人,左右指针都向中间移动
1 #881
2 #Runtime: 384 ms (Beats 53.98%)
3 #Memory: 18.9 MB (Beats 18.14%)
4
5 class Solution(object):
6 def numRescueBoats(self, people, limit):
7 """
8 :type people: List[int]
9 :type limit: int
10 :rtype: int
11 """
12 people.sort()
13 p1 = 0
14 p2 = len(people) - 1
15 ans = 0
16 while p1 <= p2:
17 if p1 == p2:
18 ans += 1
19 break
20 if people[p1] + people[p2] <= limit:
21 ans += 1
22 p1 += 1
23 p2 -= 1
24 else:
25 ans += 1
26 p2 -= 1
27 return ans
28