Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/maximize-happiness-of-selected-children/description
: 3075. Maximize Happiness of Selected Children
: 給你一個正整數陣列happiness，我們可以從裡面挑出k個數字相加，每挑出一個數字其他
: 數字就會遞減，遞減最多只會遞減為0，求出怎麼挑可以得到最大和。
: 思路：
: 1.排序，每次都挑最大的然後挑k個，下次挑的時候要減去已經挑的數量。
: py code:
: ---------------------------------------
: class Solution:
:     def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
:         happiness.sort(reverse=True)
:         res = 0
:         for i, x in enumerate(happiness[:k]):
:             if x <= i:
:                 break
:             res += x - i
:         return res
: ---------------------------------------
思路:
一樣排序 本來想建堆 不過我現在腦子像一團糨糊
還是用習慣的寫法就好

Python Code:
class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort()
        res = 0
        for i in range(k):
            x = happiness[-1]-i
            if x > 0:
                res += x
                happiness.pop()
            else:
                break

        return res

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.143.130 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715265071.A.E23.html
→ SecondRun: 今天也滿簡單的
→ sustainer123: 確實 難一點我就死了
推 ILoveErr: 大師
推 DJYOSHITAKA: 用max heap結果只贏10% 我要去床上躺平了
→ sustainer123: 我剛想了一下 建堆的時間複雜度是nlogn
→ sustainer123: 排序也是nlogn 好像沒差
→ digua: 大師
推 wu10200512: 別卷了
推 JIWP: 別卷了
→ cities516: Happy synthesizer