【Day 67 】2023-01-06 - 881. 救生艇

[azl397985856]

881. 救生艇

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/boats-to-save-people/

前置知识

暂无

题目描述

第 i 个人的体重为 people[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 <= 50000 1 <= people[i] <= limit <= 30000

[FlipN9]

/**
    因为船的 max weight of limit是固定的, 每次只能载两人
    用双指针指向最轻 和 最重,
    如果最重和最轻超过 limit, 最重也只能自己一艘船, people[i] <= limit 

    除了默认的 MergeSort 之外, 如果用 bucket sort 然后更改 people, 能将 TC 降至 O(N)

    Approach 1 MergeSort:            TC: O(NlogN)    SC: O(1)
    Approach 2 BucketSort & Inplace: TC: O(N)        SC: O(N)
*/
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int[] bucket = new int[limit + 1];
        for (int v : people) 
            bucket[v]++;
        int idx = 0, N = people.length;
        for (int i = 1; i <= limit && idx < N; i++) {
            while (bucket[i]-- > 0)
                people[idx++] = i;
        }
        int l = 0, r = N - 1, res = 0;
        while (l <= r) {
            if (people[l] + people[r] <= limit)
                l++;
            r--;
            res++;
        }
        return res;
    }
}

class Solution1 {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int N = people.length;
        int lo = 0, hi = N - 1;
        int res = 0;
        while (lo <= hi) {
            if (people[lo] + people[hi] <= limit) 
                lo++;
            hi--;
            res++;
        }
        return res;
    }
}

[snmyj]

class Solution {    //greedy
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n=people.size(),ans=0;
        sort(people.begin(),people.end());
        for(int i=n-1;i>=0;i--){
             if(people[i]==limit) {
                 ans++;
                 people.erase(people.begin()+i);
                 n--;
                 continue;
                 }
             for(int j=0;j<=i-1;j++){
                 int cnt=0;
                 if(people[i]+people[0]>limit){
                     ans++;
                    people.erase(people.begin()+i);
                    n--;
                    break;

                 }
                 if(people[i]+people[j]==limit){
                     ans++;
                    people.erase(people.begin()+i);
                     people.erase(people.begin()+j);
                    n--;
                    break;

                 }
                 if(people[i]+people[j]>limit){
                     ans++;
                      people.erase(people.begin()+i);
                      people.erase(people.begin()+j-1);
                     i=n-1;

                     break;
                 }
                 if(cnt==i-1){
                    ans++;
                      people.erase(people.begin()+i);
                      people.erase(people.begin()+i-1); 
                      n=n-2;
                 }
              }

        }
        return ans;

    }
};

[buer1121]

class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int:

双指针思想，先放最重的，再看能否放最轻的

    people.sort()
    l,r=0,len(people)-1
    res=0

    while l<r:
        total=people[l] + people[r]
        if total>limit:
            r-=1
            res+=1
        else:
            r-=1
            l+=1
            res+=1
    if l==r:
        return res+1
    return res

[Abby-xu]

思路

Sorting + ...

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort(reverse=True)
        i, j = 0, len(people) - 1
        while i <= j:
            if people[i] + people[j] <= limit: j -= 1
            i += 1
        return i

复杂度

O(nlogn)

[JancerWu]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length, ans = 0;
        for (int i = 0, j = n-1; i <= j;) {
            if (people[i] + people[j] <= limit) {
                i++;
                j--;
            } else {
                j--;
            }
            ans++;
        }
        return ans;
    }
}

[Elsa-zhang]

# 881. 救生艇
''' 第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit
    每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit
    返回载到每一个人所需的最小船数 (保证每个人都能被船载)
'''

class Solution:
    def numRescueBoats(self, people: list[int], limit: int):
        ans = 0
        people = sorted(people)
        n = len(people)

        left, right = 0, n-1
        while left <= right:
            if people[left]+people[right]>limit:
                right-=1
            else:
                left+=1
                right-=1
            ans+=1

        return ans

[tiandao043]

思路

双指针

代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(),people.end());
        int n=people.size();
        int l=0;
        int r=n-1;
        int ans=0;
        while(l<=r){
            if(l!=r && people[r]+people[l]<=limit){
                r--;
                l++;
                ans++;
            }else{
                r--;
                ans++;
            }
        }
        // int temp=limit;
        // vector<bool> vis(n,false);
        // for(int i=n-1;i>=0;i--){
        //     if(vis[i]==false){
        //       if(limit>=people[i]){
        //         temp=limit-people[i];
        //         vis[i]=true;                
        //     }                        
        //     int ind=-1;
        //     for(int j=i-1;j>=0;j--){
        //         if(vis[j]==false){
        //             // cout<<j<<endl;
        //             if(temp>=people[j]){
        //                 ind=j;
        //                 break;
        //             }
        //         }
        //     }
        //     // cout<<ind<<endl;
        //     if(ind<0){
        //         ans++;
        //     }else{
        //         vis[ind]=true;
        //         ans++;
        //     }

        //     }

        // }
        return ans;
    }
};

O(nlogn) O(1)

[Jetery]

881. 救生艇

思路

贪心, 优先让最小的和最大的匹配

代码 (cpp)

class Solution {
public:
    int numRescueBoats(vector<int>& p, int limit) {
        sort(p.begin(), p.end());
        int i = 0, j = p.size() - 1, ans = 0;
        while (i <= j) {
            if (p[i] + p[j] <= limit) i++;
            j--;
            ans++;
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[A-pricity]

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = (people, limit) => {
    if ( people.sort((a,b)=>a-b)[0] >= limit )return people.length
    let res = 0
    for( let i = 0,j = people.length-1 ; i <= j ; people[i] + people[j] <= limit && i++ , j--){
        res++
    }
    return res
};

[RestlessBreeze]

code

class Solution {
public:
    int numRescueBoats(vector<int> &people, int limit) {
        int ans = 0;
        sort(people.begin(), people.end());
        int light = 0, heavy = people.size() - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] > limit) {
                --heavy;
            } else {
                ++light;
                --heavy;
            }
            ++ans;
        }
        return ans;
    }
};

[bookyue]

code

    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);

        int res = 0;
        int left = 0;
        int right = people.length - 1;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            res++;
        }

        return res;
    }

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        int res = 0;

        while(i <= j){
            if(people[i] + people[j] <= limit)
                i++;
            j--;
            res++;
        }
        return res;
    }
}

[mayloveless]

思路

排序人，最大和最小配对，如果小于limit就算一个船，不行则最大自己算一个。

代码

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort((a,b) => a-b);

    let res = 0;
    let right = people.length-1;
    let left = 0;
    while(left <=right) {
        if (people[right] + people[left] <= limit) {
            left ++;
        }
        res++;
        right--;
    }
    return res;
};

复杂度

时间：O(nlong) 排序 空间：O(nlong) 排序

[klspta]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        if(people == null || people.length == 0 || limit < 0){
            return -1;
        }

        Arrays.sort(people);
        if(people[people.length - 1] > limit){
            return -1;
        }

        int lessR = -1;
        for(int i = people.length - 1; i >=0; i--){
            if(people[i] <= limit / 2){
                lessR = i;
                break;
            }
        }

        if(lessR == -1){
            return people.length;
        }

        int L = lessR;
        int R = lessR + 1;
        int noUsed = 0;
        while(L >= 0){
            int solved = 0;
            while(R < people.length && people[L] + people[R] <= limit){
                R++;
                solved++;
            }
            if(solved == 0){
                noUsed++;
                L--;
            }else{
                L = Math.max(-1, L - solved);
            }
        }

        return people.length - 1 - lessR + ((noUsed + 1) >> 1);
    }
}

[klspta]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int res = 0;
        for(int i = 0, j = people.length - 1; i <= j; j--){
            if(people[i] + people[j] <= limit){
                i++;
            }
            res++;
        }
        return res;
    }
}

[Alexno1no2]

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people) - 1
        res = 0

        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
            j -= 1
            res += 1
        return res

[paopaohua]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        int res = 0;

        while(i <= j){
            if(people[i] + people[j] <= limit)
                i++;
            j--;
            res++;
        }
        return res;
    }
}

[saitoChen]

思路

贪心算法

代码

const numRescueBoats = (people, limit) => {
  people.sort((a, b) => a - b)
  let ship = 0
  let lightest = 0, heavy = people.length - 1
  while(lightest <= heavy) {
    if (people[lightest] + people[heavy] <= limit) {
      lightest++
    }
    heavy--
    ship++
  }

  return ship
}

[bwspsu]

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        res = 0
        l = 0
        r = len(people) - 1
        people.sort()

        while l < r:
            total = people[l] + people[r]
            if total > limit:
                r -= 1
                res += 1
            else:
                r -= 1
                l += 1
                res += 1
        if (l == r):
            return res + 1
        return res

[MaylingLin]

思路

---

排序+双指针：对people体重升序排序；最轻的人和最重的人体重相加若小于船载重即可同时运载两人。

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        count = 0
        l = 0
        r = len(people) - 1
        people.sort()

        while l < r:
            total = people[l] + people[r]
            if total > limit:
                r -= 1
                count += 1
            else:
                r -= 1
                l += 1
                count += 1
        if l == r:
            return count + 1
        return count

复杂度

---

• Time: $O(nlogn)$
• Space: $O(1)$

[whoam-challenge]

class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: ans = 0 people.sort() light, heavy = 0, len(people) - 1 while light <= heavy: if people[light] + people[heavy] > limit: heavy -= 1 else: light += 1 heavy -= 1 ans += 1 return ans