leetcode 881 救生艇
2020-01-20 本文已影响0人
Arsenal4ever
思路:双指针
第一种不移动指针,往外弹元素;第二种移动指针,首尾两人之和如果大于限重,则第一个人坐船,否则两个人做。
class Solution(object):
def numRescueBoats(self, people, limit):
"""
:type people: List[int]
:type limit: int
:rtype: int
"""
people.sort(key= lambda x: -x)
answer = 0
while people:
i, j = 0, len(people) - 1
if people[i] + people[j] > limit:
people.pop(i)
elif i != j:
people.pop(j)
people.pop(i)
else:
people.pop(i)
answer += 1
return answer
上面解法比下面慢:
class Solution(object):
def numRescueBoats(self, people, limit):
"""
:type people: List[int]
:type limit: int
:rtype: int
"""
people.sort(reverse=True)
answer = 0
i, j = 0, len(people) - 1
while i <= j:
if people[i] + people[j] <= limit:
i += 1
j -= 1
else:
i += 1
answer += 1
return answer