leetcode881 -- Boats to Save People

leetcode881 -- Boats to Save People

题目

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)

解释,即给了一些人的重量和船的极限,每个船最多带俩人,问最少需要多少个船。

先来想一想,该如何分配才会比较合量,如果两个体重较轻的人坐一起呢,这样有可能他们俩的体重还没有船重,没有充分利用船的极限,如果两个重的人坐在一起呢,就可能超重,所以最好的办法就是一个重的和一个轻的坐一起。

所以做法是先给体重排一个序,然后从前从后各取一个,如果加起来体重没有超过船的极限的话,oK,如果超了的话,就让重的他自己坐一个。

class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        #people.sort()
        # 1,2,2,3,limit=3
        # 1,2,4,5,limit=6.  
        
        people.sort()
        i,j = 0, len(people)-1
        res = 0
        while i<=j:
            summ = people[i]+people[j]
            if summ <= limit:
                res +=1
                i += 1
                j -= 1
                
            else:
                res += 1
                j -= 1
            
        return res

可以改成下面这样

class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        #people.sort()
        # 1,2,2,3,limit=3
        # 1,2,4,5,limit=6.  
        
        people.sort()
        i,j = 0, len(people)-1
        res = 0
        while i<=j:
            summ = people[i]+people[j]
            if summ <= limit:
                i += 1       
            res += 1
            j -= 1
            
        return res

其实可以这样理解, 每一次让一个船去选择该带哪两个人或者一个人,所以无论是带两个人还是带一个人,res 都要加1, 而且无论是带两个人还是带一个人,后面那个一定会带着, 所以每次都是j -= 1, 只有当两个人的体重没有超过极限的时候才会带着轻的那个人. 即加的那个判断。

为何是 while i<= j

因为会出现这种情况,比如[1,2,2,3], limit 是3的时候, 那么第一次带3, 第二次带1,2, 这时候会发现i+=1 ,j-=1 之后 i和j相等了,所以应该是”i<=j”. 其实更严格的应该是这样写

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        
        i,j = 0, len(people)-1
        
        people.sort()
        res = 0
        
        while i<=j:
            if i==j:
                summ = people[i]   # 因为这时候i和j是重合的, 
            else:
                summ = people[i]+people[j]
            
            res += 1
            j -= 1
            
            if summ <= limit:
                i += 1
                
        return res

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦