国产操作系统生态圈推动信息安全与技术自主发展的新机遇
839
2022-10-20
[leetcode] 1052. Grumpy Bookstore Owner
Description
Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3Output: 16Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Note:
1 <= X <= customers.length == grumpy.length <= 20000.0 <= customers[i] <= 1000.0 <= grumpy[i] <= 1.
分析
题目的意思是:给你一个数组,把其中grumpy为0的位置加起来,然后给了你一个X,你可以把X范围内的数也加起来,求总的最大值。我第一次看题目没看懂,后面发现懂了,好像X就是一个窗口,除了为0的位置的数,还有滑动窗口里面的数也要加起来。我顿时看见这个慌了神,看了别人的参考代码才发现需要用一个滑动窗口找到X覆盖范围的最大值,然后重新加上grumpy位置为0的数就行了。
代码
class Solution: def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int: i=0 max_save=0 cur=0 n=len(customers) for j in range(n): if(j-i+1>X): if(grumpy[i]): cur-=customers[i] i+=1 if(grumpy[j]): cur+=customers[j] max_save=max(max_save,cur) s=sum(customers[i] for i in range(n) if(grumpy[i]==0)) return s+max_save
参考文献
[LeetCode] Python 3 Sliding window
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~