【Day 67 】2022-02-16 - 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

[dahaiyidi]

Problem

[881. 救生艇](https://leetcode-cn.com/problems/boats-to-save-people/)

难度中等209

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

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

返回 承载所有人所需的最小船数 。

---

Note

• 先排序
• 最轻的i，与最重的j若小于等于limit，则他们俩可以在一条船
• 否则j向轻的一侧移动

---

Complexity

• 时间O：nlogn
• 空间O：logn

---

Python

C++

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int i = 0;
        int j = people.size() - 1;

        int num = 0;
        while(i < j){
            if(people[i] + people[j] <= limit){
                num++;
                i++;
                j--;                
            }
            else if(people[i] + people[j] > limit){
                j--;
            }
        }
        return people.size() - num;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[linyang4]

思路

贪心+双指针

1. 对 people 从小到大排序
2. 创建2个指针, left 和 right, 分别指向体重最小和最大的人
3. 从 people 中取最小的的最大的相加
   • 如果加和大于 limit, 大的单独上船, right--
   • 如果加和小于等于 limit, 2人上同一条船, left++, right--

代码(JavaScript)

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

复杂度

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)

[fornobugworld]

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

[hx-code]

class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: visited = set() def dfs(people, limit, i, remain): if (i >= len(people)): return 0 ans = len(people) for j in range(len(people)): if j in visited: continue visited.add(j)

这个时候需要增加一个新船

            if (people[j] > remain):
                ans = min(ans, 1 + dfs(people, limit, i + 1, limit - people[j]))
            # 无需增加新船
            else:
                ans = min(ans, dfs(people, limit, i + 1, remain - people[j]))
            visited.remove(j)
        return ans
    return 1 + dfs(people, limit, 0, limit)

[zzzpppy]

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

[xinhaoyi]

class Solution { public int numRescueBoats(int[] people, int limit) { //利用排序从小到大，我们保证每个人都能被载的前提所需的最小船数，也就是说我们要尽可能每个船都载满乘客。 //由于每个船只能载两个乘客，故利用双指针从最小端与最大端取两名乘客判定是否小于limit，是则满足船载，船数加1。 //否则说明最大端乘客需要独自乘船。右指针左移，左指针不动。 //优化：一旦找到第一对两两配对的乘客，则剩余乘客皆能两两配对，奇数会使得剩余一名乘客独自乘船。 Arrays.sort(people); int ans=0; if(people.length==1)return 0; int left=0,right=people.length-1; while(left<=right){ if(people[left]+people[right]<=limit){ ans++; left++; right--; } else { right--; ans++; } } return ans; } }

[ChenJingjing85]

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

[rzhao010]

    public int numRescueBoats(int[] people, int limit) {
        int res = 0;
        Arrays.sort(people);
        int light = 0, heavy = people.length - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {
                ++light;
            }
            --heavy;
            ++res;
        }
        return res;
    }

Complexity Time: O(nlogn) Space: O(logn)

[15691894985]

【Day 67】881. 救生艇

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

思路：对people的载重进行排序，先最大和最小的是否满足limit 不满足看第二大和最小的，否则最后单独做

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

复杂度分析：

• 时间复杂度：O(n*logn) 排序需要的时间
• 空间复杂度：O（1）记录count所需的时间

[machuangmr]

代码

class Solution {
    // 排序，然后左右结合取数，证明就是1,2,3,4 1和4尽量走，而不是4和2尽量走，因为2,4可以走，那么2,3一定可以走，贪心啊。。
    // 
    public int numRescueBoats(int[] people, int limit) {
        int result = 0;
        int r = people.length - 1;
        int l = 0;
        Arrays.sort(people);
        while (l <= r) {
            if (l == r) {
                result++;
                break;
            }

            if (people[r] + people[l] > limit) {
                result++;
                r--;
            } else {
                result++;
                r--;
                l++;
            }
        }

        return result;
    }
}

[CodeFarmersWorld]

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

[taojin1992]

// try combining lightest and heaviest to achieve min
// time: O(nlogn)
// space: O(1)

// [1,1,2,2,3], l=3
// 3

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0, right = people.length - 1;
        int num = 0;
        while (left <= right) { // at least remain one person

            // at least 2 people left, cannot combine
            while (left != right && people[left] + people[right] > limit) {
                // only put heavier
                num++;
                right--;
            }

            left++;
            right--;
            num++;
        }
        return num;
    }
}

[for123s]

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

[cszys888]

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

time complexity: O(nlogn) space complexity: O(logn)

[JudyZhou95]

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

        boats = 0
        l, r = 0, len(people) - 1

        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1

            r -= 1
            boats += 1

        return boats

[tian-pengfei]

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        //先为大的排序，最终的结果才是最小的 小石头 中石头 大石头 如果大石头和小石头结合留下的是中石头，小石头与中石头结构留下的是大石头，，，，留下中石头必留下小石头有更多的变小的可能性
        sort(people.begin(),people.end());
        int count = 0;
        int min =0;
        int max = people.size()-1;
        while(min<max) {
            if(people[min]+people[max]<=limit){
                min++;
            }
            max--;
            count++;
        }
        if(min==max){
            count++;
        }
        return count;
    }
};

[Jay214]

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort((a, b) => b - a)
    let ans = 0
    let j = 0
    while (j < people.length) {
        if (people[j] === limit) {
            ans += 1
            j++
        } else {
            for (let k = j+1; k < people.length; k++) {
                if ((people[j] + people[k]) <= limit) {
                    while (k++ < people.length-1) {
                        people[k] = people[k+1]
                    }
                    people.length = people.length - 1
                    break
                }
            }
            ans += 1
            j++
        }
    }
    return ans
};