ผลิตภัณฑ์ของตัวเลข K สุดท้ายใน C++

สมมติว่าเรามีการใช้งานคลาสที่เรียกว่า ProductOfNumbers ที่รองรับสองวิธี -

add(int num):เพิ่มตัวเลขที่ด้านหลังรายการตัวเลขปัจจุบัน
getProduct(int k):ส่งคืนผลิตภัณฑ์ของตัวเลข k สุดท้ายในรายการปัจจุบัน

เราสามารถสรุปได้ว่ารายการปัจจุบันมีตัวเลขอย่างน้อย k เสมอ ตัวอย่างเช่น หากอินพุตเป็น − add(3), add(0), add(2), add(5), add(4), getProduct(2), getProduct(3), getProduct(4), เพิ่ม (8), getProduct(2) จากนั้นผลลัพธ์จะเป็น (หลังจากการเรียกใช้ฟังก์ชันแต่ละครั้ง) -

<ก่อน>[3], [3, 0], [3, 0, 2], [3, 0, 2, 5], [3, 0, 2, 5, 4], จากนั้น (5 * 4) =20 จากนั้น (2 * 5 * 4) =40 จากนั้น (0 * 2 * 5 * 4) =0 จากนั้น [3, 0, 2, 5, 4, 8] จากนั้น (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 ใช้เนมสเปซ std;คลาส ProductOfNumbers {สาธารณะ:vector  dq; ProductOfNumbers () { dq.push_back (1); } เพิ่มเป็นโมฆะ (int num) { if(num ==0){ dq.clear(); dq.push_back(1); } อื่น ๆ { dq.push_back(dq.back() * num); } } int getProduct (int k) { int n =(int)dq.size (); กลับ 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)); ศาล <<(ob.getProduct(2)) < อินพุต
 เพิ่ม(3)เพิ่ม(0)เพิ่ม(2)เพิ่ม(5)เพิ่ม(4)getProduct(2)getProduct(3)getProduct(4)เพิ่ม(8)getProduct(2)
 ผลลัพธ์
 2040032