LeetCode 1352. Product of the Last K Numbers(维护前缀和)

题目链接

题意:

维护一个列表,两个操作add和getnum(k),让你输出每次列表最后的k个数的和

思路:

操作很多,大概有4w个operation且k最大为4w,所以暴力查询肯定会T。
这是就需要空间换时间,$O(N)$空间维护一个前缀和,显然如果列表中出现0则前面的即可清0,否则继续维护,最后$O(1)$查询输出结果即可!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ProductOfNumbers:

def __init__(self):
self._list = [1]
def add(self, num: int) -> None:
if not num:
self._list = [1]
else:
self._list.append(self._list[-1] * num)
return None
def getProduct(self, k: int) -> int:
if len(self._list) <= k:
return 0
else:
return self._list[-1] // self._list[- (k + 1)]


-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 1352. Product of the Last K Numbers(维护前缀和)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年02月17日 - 16:02

最后更新:2020年02月17日 - 16:02

原始链接:https://statusrank.xyz/articles/7e1aca4b.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: