Tích của K số cuối cùng trong C ++

Giả sử chúng ta có triển khai lớp được gọi là ProductOfNumbers hỗ trợ hai phương thức -

add (int num):Điều này thêm số num vào phía sau danh sách các số hiện tại.
getProduct (int k):Trả về tích của k số cuối cùng trong danh sách hiện tại.

Chúng ta có thể giả sử rằng danh sách hiện tại luôn có ít nhất k số. Vì vậy, ví dụ:nếu đầu vào giống như - thêm (3), thêm (0), thêm (2), thêm (5), thêm (4), getProduct (2), getProduct (3), getProduct (4), add (8), getProduct (2), thì đầu ra sẽ là (sau mỗi lần gọi hàm) -

[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.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Trong phần khởi tạo, nó sẽ tạo một mảng và đặt 1 vào đó
Phương thức add () sẽ nhận num
nếu num bằng 0, thì hãy xóa mảng và chèn 1, nếu không hãy chèn last_element * num vào mảng
Phương thức getProduct () sẽ lấy k làm đầu vào
n:=kích thước của mảng
nếu k> n - 1 thì trả về 0, ngược lại thì dp [n - 1] / dp [n - k - 1]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

add(3)
add(0)
add(2)
add(5)
add(4)
getProduct(2)
getProduct(3)
getProduct(4)
add(8)
getProduct(2)

Đầu ra