数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中最后K个数的乘积
假设我们需要实现一个名为ProductOfNumbers的类，它支持两种方法：
add(int num)：将数字num添加到当前数字列表的末尾。
getProduct(int k)：返回当前列表中最后k个数字的乘积。
我们可以假设当前列表始终至少包含k个数字。例如，如果输入为：add(3), add(0), add(2), add(5), add(4), getProduct(2), getProduct(3), getProduct(4), add(8), getProduct(2)，则输出将为（每次函数调用后）：
[3], [3, 0], [3, 0, 2], [3, 0, 2, 5], [3, 0, 2, 5, 4], then (5 * 4) = 20, then (2 * 5 * 4) = 40, then (0 * 2 * 5 * 4) = 0, then [3, 0, 2, 5, 4, 8], then (4 * 8) = 32.
为了解决这个问题，我们将遵循以下步骤：
在初始化部分，创建一个数组，并在其中放入1。
add()方法将接收num作为输入。
如果num为0，则清除数组，并插入1；否则，将last_element * num插入数组。
getProduct()方法将接收k作为输入。
n := 数组的大小
如果k > n – 1，则返回0；否则返回dp[n - 1] / dp[n – k – 1]
示例 (C++)
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class ProductOfNumbers {
public:
vector <int> dq;
ProductOfNumbers() {
dq.push_back(1);
}
void add(int num) {
if(num == 0){
dq.clear();
dq.push_back(1);
}
else{
dq.push_back(dq.back() * num);
}
}
int getProduct(int k) {
int n = (int)dq.size();
return k > n - 1? 0 : dq[n - 1] / dq[n - k - 1];
}
};
main(){
ProductOfNumbers ob;
(ob.add(3));
(ob.add(0));
(ob.add(2));
(ob.add(5));
(ob.add(4));
cout << (ob.getProduct(2)) << endl;
cout << (ob.getProduct(3)) << endl;
cout << (ob.getProduct(4)) << endl;
(ob.add(8));
cout << (ob.getProduct(2)) << endl;
}输入
add(3) add(0) add(2) add(5) add(4) getProduct(2) getProduct(3) getProduct(4) add(8) getProduct(2)
输出
20 40 0 32
更新于：2020年4月29日
271 次浏览
广告