leetcode和算法----日更

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
上一篇 下一篇

猜你喜欢

热点阅读