1052. Grumpy Bookstore Owner

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium #sliding-window

LeetCode Static

Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня.

Пример:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3

Output: 16

C# решение

сопоставлено/оригинал

public class Solution {
    public int MaxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.Length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = Math.Max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.size(); i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

Java решение

сопоставлено/оригинал

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = Math.max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

JavaScript решение

сопоставлено/оригинал

public class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        int additionalSatisfied = 0;
        int maxAdditionalSatisfied = 0;
        
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            } else {
                additionalSatisfied += customers[i];
            }
            
            if (i >= minutes) {
                if (grumpy[i - minutes] == 1) {
                    additionalSatisfied -= customers[i - minutes];
                }
            }
            
            maxAdditionalSatisfied = Math.max(maxAdditionalSatisfied, additionalSatisfied);
        }
        
        return totalSatisfied + maxAdditionalSatisfied;
    }
}

Python решение

сопоставлено/оригинал

def maxSatisfied(customers, grumpy, minutes):
    total_satisfied = 0
    additional_satisfied = 0
    max_additional_satisfied = 0

    for i in range(len(customers)):
        if grumpy[i] == 0:
            total_satisfied += customers[i]
        else:
            additional_satisfied += customers[i]
        
        if i >= minutes:
            if grumpy[i - minutes] == 1:
                additional_satisfied -= customers[i - minutes]
        
        max_additional_satisfied = max(max_additional_satisfied, additional_satisfied)

    return total_satisfied + max_additional_satisfied

Go решение

сопоставлено/оригинал

package main

import (
    "fmt"
)

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    totalSatisfied := 0
    additionalSatisfied := 0
    maxAdditionalSatisfied := 0

    for i := 0; i < len(customers); i++ {
        if grumpy[i] == 0 {
            totalSatisfied += customers[i]
        } else {
            additionalSatisfied += customers[i]
        }

        if i >= minutes {
            if grumpy[i - minutes] == 1 {
                additionalSatisfied -= customers[i - minutes]
            }
        }

        if additionalSatisfied > maxAdditionalSatisfied {
            maxAdditionalSatisfied = additionalSatisfied
        }
    }

    return totalSatisfied + maxAdditionalSatisfied
}

Algorithm

Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

Пройди по массиву, используя скользящее окно для учета эффекта от техники.

Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.