search

leetcode-pp / 91alg-7-daily-check

6 stars 0 forks source link

【Day 67 】2022-06-06 - 881. 救生艇 #72

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

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

JiangWenqi commented 2 years ago

CPP

class Solution
{
public:
    int numRescueBoats(vector<int> &people, int limit)
    {
        sort(people.begin(), people.end());
        int n = people.size(), res = 0;
        for (int i = 0, j = n - 1; i <= j; j--)
        {
            if (people[i] + people[j] <= limit)
                i++;
            res++;
        }
        return res;
    }
};
djd28176 commented 2 years ago 

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int ans = 0, start = 0, end = people.length -1;
        while(start <= end){
            ans++;
            if(people[start] + people[end] <= limit){
                start++;
                end--;
            }else{
                end--;
            }
        }

        return ans;
    }
}
MichaelXi3 commented 2 years ago

Idea

贪心

Code


class Solution {
public int numRescueBoats(int[] people, int limit) {
// 把全部 people 的重量从轻到重进行排序
Arrays.sort(people);
int numBoat = 0;
    // 双指针：left 是最轻的人，right 是最重的人
    int l = 0, r = people.length - 1; 

    while (l <= r) {
        // 先试着把最重和最轻的人放在一个船，若是能放下，皆大欢喜
        if (people[l] + people[r] <= limit) {
            l++; r--;
            numBoat++;
        // 最重和最轻的人无法放在一个船的话，只能最重的人自己先走了
        } else {
            r--;
            numBoat++;
        }
    }
    return numBoat;
}

}


# Complexity
Time: O(nlog(n)) → sorting
Space: O(1)
zhiyuanpeng commented 2 years ago 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l, r = 0, len(people) - 1
        ans = 0
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
                r -= 1
            else:
                r -= 1
            ans += 1
        return ans

time O(N) space O(1)

xingchen77 commented 2 years ago 
    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
Ellie-Wu05 commented 2 years ago

思路：贪心算法

把poeple从轻到重排序：

复杂度

时间 Onlogn 空间 O1

houmk1212 commented 2 years ago

思路

贪心+双指针

代码

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

复杂度

tongyuhangg commented 2 years ago 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int ans = 0, start = 0, end = people.length -1;
        while(start <= end){
            ans++;
            if(people[start] + people[end] <= limit){
                start++;
                end--;
            }else{
                end--;
            }
        }

        return ans;
    }
}
hyh331 commented 2 years ago

Day67 思路

贪心+双指针

  1. 先把people排序，贪心：在两端设置双指针，指向体重最轻和最重的人
  2. 若加起来>limit，则坐不了一个船，只能体重最大的单独坐一个，更新右端点，且min_ships++;
  3. 若加起来<=limit，则能做一个船，更新左端点和右端点,min_ships++; 
    class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(),people.end());
    int min_ships=0;
    int left=0,right=people.size()-1;
    if(people.empty()){
        return 0;
    }
    while(left <= right){
        if(people[left]+people[right] > limit){
            right = right-1;
            min_ships++;
        }else{
            right=right-1;
            left=left+1;
            min_ships++;
        }
    }
    return min_ships;
}

    复杂度分析

    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(logn)
zqwwei commented 2 years ago

Code

    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int count = 0, left = 0, right = people.length - 1;
        while (left <= right) {
            if (left != right && people[right] + people[left] <= limit) {
                left++; right--;
            } else {
                right--;
            }
            count++;
        }

        return count;
    }
Geek-LX commented 2 years ago

6.6

思路：贪心

代码：

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)

复杂度分析：

xil324 commented 2 years ago 
class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        people = sorted(people)
        ans = 0;
        right = len(people) -1; 
        left = 0; 
        while left <= right and right < len(people):
            if people[left] + people[right] > limit:
                ans += 1;
                right -=1
            else:
                ans += 1;
                right-=1;
                left += 1;
        return ans;
ShawYuan97 commented 2 years ago

思路

每个船最多装两人，重量之和最多为limit，那么就要求每只船尽可能装更多的重量
优先将最重的人安排 如果最重的和最轻的在一起还没有超重就加上最轻的 （不用考虑非最轻的）

关键点

代码

Python3 Code:


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        """
        返回承载所有人所需的最小船只数
        """
        people.sort()
        count = 0
        s,e = 0,len(people)-1
        while s<=e:
            if people[s] + people[e] <= limit:
                e -= 1
                s += 1
            else:
                e -= 1
            count += 1
        return count

复杂度分析

令 n 为数组长度。

carterrr commented 2 years ago

class Solution { public int numRescueBoats(int[] people, int limit) { // 贪心 每次 最大 + 最小 不行就最大 (一定有 people[i] <=limit 所以不用取小的那个) Arrays.sort(people); int min = 0, max = people.length - 1, res = 0; // 双指针 while(min <= max) { if(people[min] + people[max] <= limit) { min++; } max --; // 一定有 people[i] <=limit res ++; } return res; } }

ZacheryCao commented 2 years ago

Idea

Greedy

Code

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people)-1
        count = 0
        while i<=j:
            count += 1
            if people[i]+people[j]<=limit:
                i+=1
            j-=1
        return count
L-SUI commented 2 years ago 

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort((a,b)=>a-b);
    let count = 0,i=0,len = people.length-1;
    while(people[len]>limit)  (len--,count++)
    while(i<len){
        const curr = people[len]+people[i]
        if(curr>limit) (len--,count++)
        if(curr<=limit) (len--,i++,count++)
    }
    if(len==i) count++
    return count;
};
currybeefer commented 2 years ago

int numRescueBoats(vector& people, int limit) { sort(people.begin(), people.end()); 

    int left =0; 
    int right = people.size()-1; 
    int count =0; 
    while(left <=right)
    {
        if(left!=right && people[right]+people[left]<=limit)
        {
            right--; 
            left++; 
            count++; 
        }
        else
        {
            right--; 
            count++; 
        }
    }

    return count; 
}
wychmod commented 2 years ago

思路

先排序，然后双指针，前面一个后面一个，如果前后加一块大于limit那就只取后面的。

代码

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

复杂度分析

时间复杂度：Onlogn 空间复杂度：O1

fhuang5 commented 2 years ago 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int res = 0;
        int left = 0;
        int right = people.length -1;
        while (left <= right){
            res++;
        if (people[left]+people[right]<=limit){
            left++;
        }
            right--;
        }
        return res;

    }
}
//Time: O(nlogn)
//Space: O(1) or O(log n) considering the sorting algorithm
MoonLee001 commented 2 years ago

思路

贪心

代码

var numRescueBoats = function(people, limit) {

    people.sort((a, b) => a - b);
    const n = people.length;
    let count = 0;
    let low = 0, high = n - 1;

    while(low <= high) {
        if (people[low] + people[high] <= limit) {
            low++;
        }
        count++;
        high--;
    }

    return count;
};

复杂度分析

KennethAlgol commented 2 years ago 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int res = 0;

        while (left <= right) {
            res++;
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
        }

        return res;
    }
}
Magua-hub commented 2 years ago 

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int res = 0, left = 0, right = people.size() - 1;
        while(left <= right) {
            if(people[left] + people[right] <= limit){
                res ++;
                left++;
                right --;
            }
            else {
                res ++;
                right --;
            }
        }
        return res;
    }
};
zhishinaigai commented 2 years ago

放假回来了

代码

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{
                heavy--;
                light++;
            }
            ans++;
        }
        return ans;
    }
Shuchunyu commented 2 years ago

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

Orangejuz commented 2 years ago 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l, r = 0, len(people) - 1
        ans = 0
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
                r -= 1
            else:
                r -= 1
            ans += 1
        return ans
miss1 commented 2 years ago

思路

贪心，每次尽可能多装一些重量。由于每次只能装两人，所以优先考虑最轻的人a和最重的人b，如果两个重量和大于limit，那么b就只能单独一个人乘船。

代码

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

复杂度

LQyt2012 commented 2 years ago

思路

贪心加双指针

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        left = 0
        right = len(people)-1
        count = 0
        while left <= right:
            if people[left] + people[right] <= limit:
                count += 1
                left += 1
                right -= 1
            else:
                count += 1
                right -= 1
        return count
func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)
    left := 0
    right := len(people) - 1
    count := 0
    for left <= right {
        if people[left] + people[right] <= limit {
            count++
            left++
            right--
        } else {
            count++
            right--
        }
    }
    return count
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

tensorstart commented 2 years ago 
var numRescueBoats = function(people, limit) {
  people.sort((p1, p2) => p1 - p2); // 升序
  let light = 0, heavy = people.length - 1, ans = 0;
  while (light <= heavy) {
    if (people[light] + people[heavy] <= limit) {
      light++;
      heavy--;
    } else {
      heavy--;
    }
    ans++;
  }
  return ans;
};
KWDFW commented 2 years ago

Day67

881、救生艇

javascript #贪心算法

思路

1、升序排序数组

2、先选最大重量，再找最小重量的，如果求和可以满足就选这两个

3、如果求和不能满足就选最大重量单个

代码

var numRescueBoats = function(people, limit) {
  let count = 0;//记录船的数量
  people.sort((a, b) => a - b);//升序排序
  let head = 0, tail = people.length - 1;
  //设置首尾指针
  while (head <= tail) {
    if (people[head] + people[tail] <= limit) {
      head++;
    }
    tail--;
    count++;
  }
  //如果首尾都能放在船上就都放进去，不能的话就只放首
  return count;
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(logn)

xiayuhui231 commented 2 years ago

题目

救生艇

代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
 int n = (int)people.size();
        if (n == 1) return 1;
        sort(people.begin(), people.end());
        int left = 0, right = n - 1, ans = 0; 
        long long sum = accumulate(people.begin(), people.end(), 0), count = 0;
        while(left < right) {
            if (people[left] + people[right] > limit) {
                count += people[right--];
                ++ans;
            } else {
                count += people[left++];
                count += people[right--];
                ++ans;
            }
        }
        if (sum != count)   return ans + 1;
        return ans;
    }
};
flyzenr commented 2 years ago

Code

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

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
 int n = (int)people.size();
        if (n == 1) return 1;
        sort(people.begin(), people.end());
        int left = 0, right = n - 1, ans = 0; 
        long long sum = accumulate(people.begin(), people.end(), 0), count = 0;
        while(left < right) {
            if (people[left] + people[right] > limit) {
                count += people[right--];
                ++ans;
            } else {
                count += people[left++];
                count += people[right--];
                ++ans;
            }
        }
        if (sum != count)   return ans + 1;
        return ans;
    }
};
XXjo commented 2 years ago 

var numRescueBoats = function(people, limit) {
    people = people.sort((a, b) => a - b);
    let min = 0;
    let max = people.length - 1;
    let res = 0;
    while(min <= max){
        if(people[min] + people[max] <= limit){
            min++;
            max--;
        }
        else{
            max--;
        }
        res++;
    }
    return res;
};
mo660 commented 2 years ago 
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;
    }
};
freedom0123 commented 2 years ago 

class Solution
{
public:
    int numRescueBoats(vector<int> &people, int limit)
    {
        sort(people.begin(), people.end());
        int n = people.size(), res = 0;
        for (int i = 0, j = n - 1; i <= j; j--)
        {
            if (people[i] + people[j] <= limit)
                i++;
            res++;
        }
        return res;
    }
}; ```
revisegoal commented 2 years ago

贪心

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

        while (left <= right) {
            res++;
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
        }

        return res;
    }
}
AConcert commented 2 years ago 
var numRescueBoats = function(people, limit) {
    let ans = 0;
    people.sort((a, b) => a - b);
    let light = 0, heavy = people.length - 1;
    while (light <= heavy) {
        if (people[light] + people[heavy] <= limit) {
            ++light;
        }
        --heavy;
        ++ans;
    }
    return ans;
};
yinhaoti commented 2 years ago 
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)
maggiexie00 commented 2 years ago 
def numRescueBoats(self, people: List[int], limit: int) -> int:
    people.sort()
    l,r=0,len(people)-1
    ans=0
    while l<=r:
        if people[l]+people[r]<=limit:
            ans+=1
            l+=1
            r-=1
        else:
            ans+=1
            r-=1
    return ans
houyanlu commented 2 years ago

思路

贪心+双指针：每条船尽可能的乘坐两人（最轻的和最重的尽量凑一块）

代码


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

            ans++;
        }

        return ans;
    }
};

复杂度分析

Yongxi-Zhou commented 2 years ago

思路

greedy, two pointers

代码

    class Solution(object):
        def numRescueBoats(self, people, limit):
            """
            :type people: List[int]
            :type limit: int
            :rtype: int
            """
            people.sort()
            res = 0
            lo, hi = 0, len(people) - 1
            while lo <= hi:
                if people[lo] + people[hi] > limit:
                    hi -= 1
                else:
                    lo += 1
                    hi -= 1
                res += 1
            return res

复杂度

time O(nlogn) space O(1)

xixiao51 commented 2 years ago

Idea

Greedy - choose the biggest and smallest one

Code

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

Complexity Analysis

taojin1992 commented 2 years ago 
// 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;
    }
}