資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告