C++の最後のK番号の積

2つのメソッドをサポートする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