Implement the class ProductOfNumbers
that supports two methods:
1. add(int num)
- Adds the number
num
to the back of the current list of numbers.
2. getProduct(int k)
- Returns the product of the last
k
numbers in the current list. - You can assume that always the current list has at least
k
numbers.
At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
Example:
Input ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]] Output: [null,null,null,null,null,null,20,40,0,null,32] Explanation: ProductOfNumbers productOfNumbers = new ProductOfNumbers(); productOfNumbers.add(3); // [3] productOfNumbers.add(0); // [3,0] productOfNumbers.add(2); // [3,0,2] productOfNumbers.add(5); // [3,0,2,5] productOfNumbers.add(4); // [3,0,2,5,4] productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20 productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0 productOfNumbers.add(8); // [3,0,2,5,4,8] productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32
Constraints:
- There will be at most
40000
operations considering bothadd
andgetProduct
. 0 <= num <= 100
1 <= k <= 40000
Solution: Prefix product
Use p[i] to store the prod of a1*a2*…ai
p[i] = ai*p[i-1]
If ai is 0, reset p = [1].
Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.
otherwise return p[n] / p[n – k – 1]
Time complexity: Add: O(1), getProduct: O(1)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class ProductOfNumbers { public: ProductOfNumbers(): p_(1, 1) { } void add(int num) { if (num == 0) { p_.clear(); p_.push_back(1); } else { p_.push_back(p_.back() * num); } } int getProduct(int k) { if (k >= p_.size()) return 0; // a_1*a_2*...*a_n / a_1*a_2*...*a_n-k-1. return p_.back() / p_[p_.size() - k - 1]; } private: vector<int> p_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment