[Python知识库]leetcode每日一题·救生艇问题(Python)

leetcode每日一题·救生艇问题(Python)

问题描述

题目入口

题目思路

首先分析问题，一个船最多坐两人，因此我们可以把这个问题看作两两组合的问题，并且如果最重的那个人和最轻的人加起来大于limit的话，说明最重的那个人是要一个人坐船的，此外，如果最重的人和最轻的人正好同坐一条船，那么就可以将它俩分配到一条船上去。
因此在写代码时，首先将数组排序，分别指向首尾坐标，判断当前最轻+最重是否大于limit，大于的话，最重的人坐船，船数+1，尾坐标前移，如果小于，那么最轻和最重两人一起坐船，首坐标后移，尾坐标前移，船数+1。因为考虑到最后一次人数是一人还是两人的问题，如果一人，那么首坐标和尾坐标指向同一个人时，一个人坐船离开，亦或者剩余最后两个人都坐船离开，因此判断条件为首坐标>尾坐标，跳出循环。
代码如下：

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # 代表船的个数
        n = 0
        # 排序
        people.sort()
        # 指向最轻的人的下标
        head = 0
        # 指向最重的人的下标
        tail = len(people) - 1
        while head <= tail:
            if people[head] + people[tail] > limit:
                tail -= 1
            else:
                head += 1
                tail -= 1
            n += 1
        return n