Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: ※ 引述《oin1104 (是oin的說)》之銘言：
: : 題目 :
: : 給你一串陣列customers
: : 是在第 i 分鐘 會來的customers[i] 個客人
: : 還有grumpy
: : 是在第 i 分鐘 1會生氣 或0不會生氣的老闆
: : 老闆生氣的話客人就哭哭跑掉
: : 沒生氣的話客人就可以買東西
: : 你可以痛扁老闆一次
: : 讓他不要生氣持續minutes 分鐘
: : 請問最多有多少客人可以買到東西
: 思路：
: 1.第一眼看到題目感覺是dp => 想不到 => 感覺是前綴和 => 寫起來卡卡怪怪的 =>
:   畫圖 => 感覺可以把 grumpy[i] == 0 的加起來然後再加上最長的 grumpy[i] == 1
:   對應的customers子陣列和
: 2.上面兩步就是貪婪+滑動窗口 寫出來一次就AC了
: java code
: --------------------------------------------------
: class Solution {
:     public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
:         int n = customers.length;
:         int res = 0;
:         for (int i = 0; i < n; i++) {
:             if (grumpy[i] == 0) {
:                 res += customers[i];
:             }
:         }
:         int curr_loss = 0;
:         int max_loss = 0;
:         for (int i = 0; i < n; i++) {
:             curr_loss += grumpy[i] == 1 ? customers[i] : 0;
:             if (i >= minutes) {
:                 curr_loss -= grumpy[i - minutes] == 1 ? customers[i -
: minutes] : 0;
:             }
:             max_loss = Math.max(max_loss, curr_loss);
:         }
:         return res + max_loss;
:     }
: }
: --------------------------------------------------

思路:
差不多 遇到0無腦加 遇到1就先存起來 然後i>老闆忍耐時間就開始扣

就是找到能夠加最多零的忍耐區間


Python Code:
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes:
int) -> int:
        pre = 0
        cur = 0
        result = 0

        for i in range(len(grumpy)):
            if grumpy[i] == 0:
                result += customers[i]
            else:
                pre += customers[i]
            if i >= minutes:
                if grumpy[i-minutes]:
                    pre -= customers[i-minutes]
            cur = max(cur,pre)

        return result + cur



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.140.245 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718988306.A.7FF.html
→ deatheo: 大師