每日算法系列【LeetCode 881】救生艇

简介: 每日算法系列【LeetCode 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] 来说,装了他之后船上还剩 limit-people[i] 的空间,所以第二个人要尽量装能装得下的人中最重的那个。

那如果直接这么遍历显然不行,时间复杂度是  的。所以我们先对重量进行排序,然后从最轻的人开始看,如果他能和最重的坐一个船,那就去掉他们俩,在剩下的人里继续找;如果不能的话,那么最重的人只能单独坐船,然后看能不能和第二重的人坐一个船,依次下去。

具体实现上,只需要用两个指针,一个指着最小的数,一个指着最大的数就行了,时间复杂度是  ,但是由于还得调用一次快速排序,所以最终时间复杂度是  。

当然,因为这题重量范围比较小,所以如果采用计数排序,可以进一步降低时间复杂度。

代码

双指针(c++)

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1, res = 0;
        while (l <= r) {
            res++;
            if (people[l] + people[r] <= limit) l++;
            r--;
        }
        return res;
    }
};

双指针(python)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        res, l, r = 0, 0, len(people) - 1
        while l <= r:
            res += 1
            if people[l] + people[r] <= limit:
                l += 1
            r -= 1
        return res

计数排序(c++)

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        vector<int> sp(n, 0);
        vector<int> count(limit+1, 0);
        for (int i = 0; i < n; ++i) {
            count[people[i]]++;
        }
        for (int i = 1; i <= limit; ++i) {
            count[i] += count[i-1];
        }
        for (int i = 0; i < n; ++i) {
            sp[count[people[i]]-1] = people[i];
            count[people[i]]--;
        }
        int l = 0, r = n - 1, res = 0;
        while (l <= r) {
            res++;
            if (sp[l] + sp[r] <= limit) l++;
            r--;
        }
        return res;
    }
};

计数排序(python)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        sp = [0] * len(people)
        count = [0] * (limit + 1)
        for i in people:
            count[i] += 1
        for i in range(1, limit + 1):
            count[i] += count[i-1]
        for i in people:
            sp[count[i]-1] = i
            count[i] -= 1
        res, l, r = 0, 0, len(people) - 1
        while l <= r:
            res += 1
            if sp[l] + sp[r] <= limit:
                l += 1
            r -= 1
        return res

后记

这题注意写循环的时候也有技巧的,我们实现的时候,对于最大值 people[r] ,先给他分配一条船,再看最小的人能否和他一条船,如果可以,那就顺便带上( l 加 1 ),如果不可以的话,那就 r 减 1 ,继续看下一个更重的人。

相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
21小时前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
22天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
21 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
48 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
53 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
77 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
40 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
36 0