leetcode 881. 救生艇
难度 - 中等
leetcode 881. 救生艇
题目描述
给定数组 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 * 1e4
1 <= people[i] <= limit <= 3 * 1e4
## 贪心解法
要使需要的船数尽可能地少,应当使载两人的船尽可能地多。
设 people\textit{people}people 的长度为 nnn。考虑体重最轻的人:
若他不能与体重最重的人同乘一艘船,那么体重最重的人无法与任何人同乘一艘船,此时应单独分配一艘船给体重最重的人。从 people 中去掉体重最重的人后,我们缩小了问题的规模,变成求解剩余 n−1 个人所需的最小船数,将其加一即为原问题的答案。
若他能与体重最重的人同乘一艘船,那么他能与其余任何人同乘一艘船,为了尽可能地利用船的承载重量,选择与体重最重的人同乘一艘船是最优的。从 people 中去掉体重最轻和体重最重的人后,我们缩小了问题的规模,变成求解剩余 n−2 个人所需的最小船数,将其加一即为原问题的答案。
在代码实现时,我们可以先对 people 排序,然后用两个指针分别指向体重最轻和体重最重的人,按照上述规则来移动指针,并统计答案。文章来源:https://www.toymoban.com/news/detail-637838.html
代码
/**
* 救生艇
* @param people
* @param limit
* @return
*/
public int numRescueBoats(int[] people, int limit) {
if (people.length == 1){
return 1;
}
Arrays.sort(people);
int l = 0;
int r = people.length - 1;
int ans = 0;
while (l <= r){
//如果l 和 r 能凑到一起,l++ ,去下一个位置继续判断
if (people[l] + people[r] <= limit){
l++;
}
//两种情况,上面条件如果成立,l 右移一位,r 向左移动一位,需要一个船。
//如果上面条件不成立,r 单独一条船,r 左移一位,需要一个船。
r--;
ans++;
}
return ans;
}
双指针算法
leetcode870. 优势洗牌文章来源地址https://www.toymoban.com/news/detail-637838.html
到了这里,关于leetcode 881. 救生艇(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!