Posted on 2023-04-03 16:27
Uriel 阅读(19)
评论(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