Tích Của K Số Cuối Cùng Trong C++

Giả sử chúng ta triển khai lớp ProductOfNumbers hỗ trợ hai phương thức:

• add(int num): Thêm num vào cuối danh sách 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.

Luôn giả định danh sách hiện tại có ít nhất k số. Ví dụ: add(3), add(0), add(2), add(5), add(4), getProduct(2), getProduct(3), getProduct(4), add(8), getProduct(2) → kết quả: 20, 40, 0, 32.

Để giải quyết, chúng ta làm theo các bước:

• Khởi tạo: tạo mảng, đưa 1 vào.

• add(num): nếu num == 0: xóa mảng, push 1; ngược lại push back * num.

• getProduct(k): n = kích thước mảng; nếu k > n-1 trả về 0; ngược lại trả về dq[n-1] / dq[n-k-1].

Ví dụ (C++)

Hãy xem 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];
    }
};

int 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

20 40 0 32