炒河粉的无量法师

881. 救生艇

August 26, 2021LeetCode

题目:881. 救生艇

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

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

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

刚开始读完题目在想是不是需要用动态规划?但我又不太会,那还是用回溯算法试试吧。等看完示例,思考一阵之后发现根本不用这么复杂。

首先根据题意每艘船最多只能乘坐两个人,然后题目问的是“最少多少个小船能坐下“,那么说明每人的体重都小于等于船的 limit。

那么,解题思路:首先给数组排序从大到小(从小到大也行)顺序,然后定义左右指针,数组两端的数值相加小于等于 limit 就乘坐两个人,反之就乘坐一个人。没错,这个中等的题就这么简单。

var numRescueBoats = function(people, limit) {
  people.sort((a, b) => b - a);
  let left = 0;
  let right = people.length - 1;
  let count = 0;
  while (left <= right) {
    count++;
    if (people[left] + people[right] <= limit) {
      right--;
    }
    left++;
  }
  return count;
};

野生程序猿,专业铲屎官。#Github 账号