1352. 最后 K 个数的乘积
请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
1. add(int num)
num 添加到当前数字列表的最后面。2. getProduct(int k)
k 个数字的乘积。k 个数字。题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
示例：
输入： ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]] 输出： [null,null,null,null,null,null,20,40,0,null,32] 解释： ProductOfNumbers productOfNumbers = new ProductOfNumbers(); productOfNumbers.add(3); // [3] productOfNumbers.add(0); // [3,0] productOfNumbers.add(2); // [3,0,2] productOfNumbers.add(5); // [3,0,2,5] productOfNumbers.add(4); // [3,0,2,5,4] productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20 productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40 productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0 productOfNumbers.add(8); // [3,0,2,5,4,8] productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
提示：
add 和 getProduct 两种操作加起来总共不会超过 40000 次。0 <= num <= 1001 <= k <= 40000原站题解
golang 解法, 执行用时: 148 ms, 内存消耗: 15.5 MB, 提交时间: 2023-09-11 11:42:40
type ProductOfNumbers struct {
pre [] int
}
func Constructor() ProductOfNumbers {
return ProductOfNumbers {
pre: []int{1},
}
}
func (this *ProductOfNumbers) Add(num int) {
if num == 0 {
this.pre = []int{1}
} else {
this.pre = append(this.pre, this.pre[len(this.pre)-1] * num)
}
}
func (this *ProductOfNumbers) GetProduct(k int) int {
if len(this.pre) <= k {
return 0
} else {
return this.pre[len(this.pre) - 1] / this.pre[len(this.pre) - 1 - k]
}
}
/**
* Your ProductOfNumbers object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(num);
* param_2 := obj.GetProduct(k);
*/
python3 解法, 执行用时: 192 ms, 内存消耗: 29.6 MB, 提交时间: 2023-09-11 11:42:12
class ProductOfNumbers:
def __init__(self):
self.prelst, self.prelen = [1], 1
def add(self, num: int) -> None:
if num:
self.prelst.append(self.prelst[-1] * num)
self.prelen += 1
else:
self.prelst, self.prelen = [1], 1
def getProduct(self, k: int) -> int:
return self.prelst[-1] // self.prelst[- 1 - k] if k < self.prelen else 0
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
python3 解法, 执行用时: 6856 ms, 内存消耗: 29.4 MB, 提交时间: 2023-09-11 11:41:58
class ProductOfNumbers:
def __init__(self):
self.lst = []
def add(self, num: int) -> None:
self.lst.append(num)
def getProduct(self, k: int) -> int:
return prod(self.lst[-k:])
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
cpp 解法, 执行用时: 200 ms, 内存消耗: 70.3 MB, 提交时间: 2023-09-11 11:41:32
class ProductOfNumbers {
public:
vector<int>vec,zero,pre;
int n;
ProductOfNumbers() {
vec.clear();
zero.clear();
pre.clear();
n=0;
}
void add(int num) {
n++;
vec.push_back(num);
pre.push_back(-1);
if (n>1){
if (vec[n-2]!=1 && vec[n-2]!=0) pre[n-1]=n-2;
else pre[n-1]=pre[n-2];
}
zero.push_back(num==0?1:0);
if (n>1) zero[n-1]+=zero[n-2];
}
int getProduct(int k) {
int tot=zero[n-1];
if (n-k>=1) tot-=zero[n-1-k];
if (tot>0) return 0;
int ans=1;
for (int i=n-1;i>=n-k;){
ans*=vec[i];
i=pre[i];
}
return ans;
}
};
/**
* Your ProductOfNumbers object will be instantiated and called as such:
* ProductOfNumbers* obj = new ProductOfNumbers();
* obj->add(num);
* int param_2 = obj->getProduct(k);
*/
cpp 解法, 执行用时: 176 ms, 内存消耗: 69.1 MB, 提交时间: 2023-09-11 11:41:15
class ProductOfNumbers {
public:
#define N 40010
int len,pre[N];
ProductOfNumbers() {
pre[0]=1;
len=0;
}
void add(int num) {
if (!num) len=0;
else{
pre[++len]=num;
pre[len]*=pre[len-1];
}
}
int getProduct(int k) {
if (len<k) return 0;
return pre[len]/pre[len-k];
}
};
/**
* Your ProductOfNumbers object will be instantiated and called as such:
* ProductOfNumbers* obj = new ProductOfNumbers();
* obj->add(num);
* int param_2 = obj->getProduct(k);
*/