本文主要是介绍LeetCode解法汇总881. 救生艇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:. - 力扣(LeetCode)
描述:
给定数组 people
。people[i]
表示第 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 <= 5 * 104
1 <= people[i] <= limit <= 3 * 104
解题思路:
使用贪心算法+双指针。
首先对体重进行排序,因为该题与顺序无关。
如果右指针指向的位置的人的重量大于等于limit,则右指针向左移动;
如果右指针指向的位置的人的重量小于limit,则与左指针指向的位置的人的重量进行累加,如果之和大于limit,则右指针向左移动;
如果之和小于等于limit,则说明可以装下两个人,则右指针向左移动,左指针向右移动。
当左指针的位置大于右指针时,循环结束。此时如何两者重合,则仅使用右指针的值即可。
代码:
class Solution881
{
public:int numRescueBoats(vector<int> &people, int limit){sort(people.begin(), people.end());int leftIndex = 0;int rightIndex = people.size() - 1;int count = 0;while (leftIndex <= rightIndex){if (leftIndex == rightIndex){count++;break;}if (people[rightIndex] >= limit || people[rightIndex] + people[leftIndex] > limit){rightIndex--;count++;continue;}rightIndex--;leftIndex++;count++;continue;}return count;}
};
这篇关于LeetCode解法汇总881. 救生艇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!