GuilinDev

Lc1352

05 August 2008

1352. Product of the Last K Numbers

实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：

  1. add(int num) - 将数字 num 添加到当前数字列表的最后面。
  2. getProduct(int k) - 返回当前数字列表中，最后 k 个数字的乘积。

可以假设当前列表中始终 至少 包含 k 个数字。

题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。

前缀积，注意保存最后一次出现0的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class ProductOfNumbers {
    int i;
    int prePro[];
    int j;

    public ProductOfNumbers() {
        j = 1;
        i = -1;
        prePro = new int[100001];
        prePro[0] = 1;
    }

    public void add(int num) {
        if (num == 0) {
            i = j;
            prePro[j] = 1;
        } else {
            prePro[j] = num * prePro[j - 1];
        }
        j++;
    }

    public int getProduct(int k) {
        return j - k <= i ? 0 : prePro[j - 1] / prePro[j - k - 1];
    }
}

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers obj = new ProductOfNumbers();
 * obj.add(num);
 * int param_2 = obj.getProduct(k);
 */
This site is open source. Improve this page.