Posted on 2023-04-03 16:27
Uriel 閱讀(47)
評論(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