Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

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

881. Boats to Save People

給定一陣列people 此陣列代表需要上船的人 people[i]代表此人的體重

你現在有無限艘船 船有承重上限limit 每艘船一次最多載兩個人

請回傳帶回所有人所需的最少船隻數

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)


Constraints:

1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104


思路:
排序然後two pointer

Python Code:
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        boats = 0
        light = 0
        heavy = len(people) - 1

        while light <= heavy:
            if people[light] + people[heavy] <= limit:
                light += 1
            heavy -= 1
            boats += 1

        return boats

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.123 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714790731.A.EAE.html
推 JIWP: 可以不用排序
→ JIWP: 別卷了
→ sustainer123: 要吧?
推 wu10200512: 別卷了
→ JIWP: 你用一個array 長度limit+1去記錄每個重量出現的次數
→ JIWP: 接著一樣是two pointer
推 wu10200512: 你好強
→ sustainer123: R對欸 這樣就降到O(n)
推 argorok: 大師 別卷了
→ DJYOSHITAKA: 大師...
推 SecondRun: 大師
推 digua: 大師