本文主要是介绍【Java每日一题】3.船只安排(贪心算法+双指针),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目难度:中等
主要提升:贪心算法、双指针思想
一、题目描述:
给定数组 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)
三、思路:
贪心算法是一种在计算机科学中常用的算法策略,它基于一种直观的想法:在每一步决策中都选择当前看起来最优的选择,以期望这样能够导致全局最优解。这种算法并不保证总能得到全局最优解,但在许多情况下,它能够提供足够好的近似解或者确切的最优解。所以在这个问题中,我们考虑最大值和最小值的和如果等于限制值,那就是最优解。
四、代码:
import java.util.Arrays;public class Solution {public int numRescueBoats(int[] people, int limit) {// 首先对人员进行排序Arrays.sort(people);int boats = 0;int left = 0; // 指向最轻的人int right = people.length - 1; // 指向最重的人while (left <= right) {if (people[left] + people[right] <= limit) {// 如果最轻的人和最重的人可以共乘一艘船left++;}right--; // 最重的人单独乘坐一艘船或者已经和他人共乘boats++; // 需要的船只数量加一}return boats;}public static void main(String[] args) {Solution solution = new Solution();int[] people1 = {1, 2};int limit1 = 3;System.out.println(solution.numRescueBoats(people1, limit1)); // 输出:1int[] people2 = {3, 2, 2, 1};int limit2 = 3;System.out.println(solution.numRescueBoats(people2, limit2)); // 输出:3int[] people3 = {3, 5, 3, 4};int limit3 = 5;System.out.println(solution.numRescueBoats(people3, limit3)); // 输出:4}
}
这篇关于【Java每日一题】3.船只安排(贪心算法+双指针)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!