LeetCode/1352.cpp at master · guihunkun/LeetCode · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class ProductOfNumbers
{
public:
    vector<int>vec,zero,pre;
    int n;
    ProductOfNumbers()
    {
        vec.clear();
        zero.clear();
        pre.clear();
        n=0;
    }

    void add(int num)
    {
        n++;
        vec.push_back(num);
        pre.push_back(-1);
        if(n>1) {
            if (vec[n-2]!=1 && vec[n-2]!=0) pre[n-1]=n-2;
            else pre[n-1]=pre[n-2];
        }
        zero.push_back(num==0?1:0);
        if(n>1)
            zero[n-1]+=zero[n-2];
    }

    int getProduct(int k)
    {
        int tot=zero[n-1];
        if(n-k>=1)
            tot-=zero[n-1-k];
        if(tot>0)
            return 0;
        int ans=1;
        for(int i=n-1;i>=n-k;) {
            ans*=vec[i];
            i=pre[i];
        }
        return ans;
    }
};
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */