盛日辉的博客
0%

Leetcode_881. 救生艇

发表于 分类于

题目

881. 救生艇
难度：中等

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

 

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

方法一： 贪心=排序+双指针

将people数组排序之后，用双指针的方法来做。要使船的数量尽可能少，那就让一个船上的人尽可能多，也就是让体重大的，尽可能和一个体重轻的坐一个船。两个指针i和j，一个从轻往重走，一个从重往轻走，如果可以一起坐船，两个指针一起动，boats计数自增；如果两个不能一起坐船，那就重的指针移动，计数自增；直到两个指针重合，这时候，计数还需要再自增一次。
贪心相当于思想，排序+双指针是具体的实现方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numRescueBoats(people, limit):
    people.sort()
    i, j = 0, len(people)-1
    boats = 0
    while i < j:
        if people[i]+people[j] > limit:
            j -= 1
            boats+=1
        else:
            boats+=1
            i += 1
            j -= 1
        if i==j:
            boats+=1
    return boats

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        ans = 0
        people.sort()
        light, heavy = 0, len(people) - 1
        while light <= heavy:
            if people[light] + people[heavy] > limit:
                heavy -= 1
            else:
                light += 1
                heavy -= 1
            ans += 1
        return ans

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/boats-to-save-people/solution/jiu-sheng-ting-by-leetcode-solution-0nsp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二： 贪心

这其实使我首先想到的方法，但。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def numRescueBoats(people, limit):
    d = defaultdict(int)
    i, j = limit+1, 0
    for w in people:
        d[w] += 1
        if i > w:
            i = w
        if j < w:
            j = w
    boats = 0
    while i < j:
        if d[j]==0:
            j -= 1
            continue
        if d[i] == 0:
            i += 1
            continue
        if i+j > limit:
            boats += d[j]
            j -= 1
            continue
        m = min(d[i], d[j])
        boats += m
        d[i] -= m
        d[j] -= m
        # i += (1-d[i]/1)
        # # if d[i]==0:
        # #     i-=1
        # j -= (1-d[j]/1)

    if i <= limit/2:
        boats += (d[i]+1)//2
    else:
        boats += d[i]

    return boats

说明：
这里的做法是先统计了每种体重的人数，然后再用双指针的方法根据人数来做。
每次进入循环的时候，都要先判断对应体重的人数是不是0，这是因为，如果是0而没有先做处理的话，会出现if i+j > limit:依然被执行的情况。
以为这种方法会减少时间消耗，然而并没有。

提交记录

救生艇提交记录.jpg