Product of the Last K Numbers

Description

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 both add and getProduct.
• 0 <= num <= 100
• 1 <= k <= 40000

Solution(javascript)

// Prefix Product 注意为0的情况
// const ProductOfNumbers = function () {
//   this.prefixProduct = []
//   this.nums = []
// }

// /**
//  * @param {number} num
//  * @return {void}
//  */
// ProductOfNumbers.prototype.add = function (num) {
//   this.nums.push(num)
//   if (this.prefixProduct[this.prefixProduct.length - 1] !== undefined) {
//     this.prefixProduct.push(
//       this.prefixProduct[this.prefixProduct.length - 1] * num,
//     )
//   } else {
//     this.prefixProduct.push(num)
//   }
// }

// /**
//  * @param {number} k
//  * @return {number}
//  */
// ProductOfNumbers.prototype.getProduct = function (k) {
//   // 这个地方我当时不知道怎么处理为 0 的情况
//   const { length } = this.prefixProduct
//   const index = length - k - 1
//   if (index < 0) {
//     return this.prefixProduct[length - 1]
//   }
//   if (this.prefixProduct[index] !== 0) {
//     return this.prefixProduct[length - 1] / this.prefixProduct[index]
//   }
//   let result = 1
//   while (k > 0) {
//     result *= this.nums[length - k]
//     k--
//   }
//   return result
// }


const ProductOfNumbers = function () {
  this.prefixProduct = []
}

/**
 * @param {number} num
 * @return {void}
 */
ProductOfNumbers.prototype.add = function (num) {
  if (num === 0) {
    this.prefixProduct = []
  } else if (this.prefixProduct[this.prefixProduct.length - 1] !== undefined) {
    this.prefixProduct.push(
      this.prefixProduct[this.prefixProduct.length - 1] * num,
    )
  } else {
    this.prefixProduct.push(num)
  }
}

/**
 * @param {number} k
 * @return {number}
 */
ProductOfNumbers.prototype.getProduct = function (k) {
  // 这个地方我当时不知道怎么处理为 0 的情况
  const { length } = this.prefixProduct
  const index = length - k - 1
  return length < k ? 0 : this.prefixProduct[length - 1] / (this.prefixProduct[index] || 1)
}