C ++中最后K个数的乘积

假设我们有一个名为ProductOfNumbers的实现，它支持两种方法-

• add（int num）：这会将数字num添加到当前数字列表的后面。

• getProduct（int k）：返回当前列表中最后k个数字的乘积。

我们可以假设当前列表始终至少包含k个数字。因此，例如，如果输入类似-add(3)，add，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