0%

LeetCode 881. Boats to Save People

Posted on In

题目

原题在此

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

解析

方法一

将people排序, 然后判断情况上船:

  1. 当前最轻的和最重的不能坐一起 $\Rightarrow$ 最重的不能和任何人共坐一条船 $\Rightarrow$ 最重的人单独上船 $\Rightarrow$ tailPointer--;
  2. 当前最轻的和最重的能坐一起 $\Rightarrow$ 都上船 $\Rightarrow$ tailPointer--; headPointer++

重复上述过程直至 headPointer $\geq$ tailPointer

方法二

与方法一类似, 创建一个limit + 1长的数组当作map, 省去排序步骤.

代码

方法一(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numRescueBoats(vector<int>& people, int lim) {
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1;
        int res = 0;
        while(l <= r) {
            if (people[l] + people[r] <= lim) l++;
            r--;
            res++;
        }
        return res;
    }
};

方法二(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        vector<int> buckets(limit+1, 0); int n=people.size();
        for(int i=0; i<n; i++) buckets[people[i]]++;
        int l=0, r=limit, ans=0;
        while(l<=r) {
            while(l<=r && buckets[l]<=0) l++;
            while(l<=r && buckets[r]<=0) r--;
            if (buckets[l]<=0 && buckets[r]<=0) break;
            ans++;
            if (l+r<=limit) buckets[l]--;
            buckets[r]--;
        }
        return ans;
    }
};