[LeetCode] 1352. Product of the Last K Numbers #1352

grandyang · 2019-05-30T16:35:06Z

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

ProductOfNumbers() Initializes the object with an empty stream.
void add(int num) Appends the integer num to the stream.
int 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.

The test cases are generated so that, 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:

0 <= num <= 100
1 <= k <= 4 * 104
At most 4 * 104 calls will be made to add and getProduct.
The product of the stream at any point in time will fit in a 32-bit integer.

这道题给了一个数据流，让返回最后k个数字的乘积，这里博主也尝试了最简单粗暴的解法，居然没有超时，可以通过。使用一个数组 data 来记录数据流，当调用 add 函数时，将数字加入 data 中。在 getProduct 函数中，遍历末尾k个数字，将它们乘起来返回即可，参见代码如下：

解法一：

class ProductOfNumbers {
public:
    ProductOfNumbers() {}
    
    void add(int num) {
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int n = data.size(), res = 1;
        for (int i = 0; i < k; ++i) {
            res *= data[n - 1 - i];
        }
        return res;
    }

private:
    vector<int> data;
};

我们也可以在上面的解法上稍微做一些优化，这里的优化思路就是快速判断若数组末尾k个数字中有0存在的话，就马上返回0，而不用再计算k个数字的乘积。这里需要记录数组中所有0出现的位置，这里使用另外一个数组 zeros 来记录所有0的位置，在 add 函数中，判断若 num 为0，则用当前 data 数组的大小来当作0的位置，加入到 zeros 数组中，然后还是要将 num 加入到 data 中。在 getProduct 函数中，首先判断末尾k个数字中是否有0，最有可能出现在末尾k个数字中的0就是 zeros 数组中的最后一个位置，判断方法是用 zeros 数组的最后一个数组（若存在的话）和 n - k 相比较，若其大于等于 n - k，直接返回0。否则还是老老实实的将末尾k个数字相乘吧，参见代码如下：

解法二：

class ProductOfNumbers {
public:
    ProductOfNumbers() {}
    
    void add(int num) {
        if (num == 0) {
            zeros.push_back(data.size());
        }
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int n = data.size(), res = 1;
        if (zeros.size() != 0 && zeros.back() >= n - k) return 0;
        for (int i = 0; i < k; ++i) {
            res *= data[n - 1 - i];
        }
        return res;
    }

private:
    vector<int> data, zeros;
};

再来看一种极大优化运行时间的解法，这里创建一个累加积数组 prod，其中 prod[i] 表示末尾 n-i 个数字的乘积，则末尾k个数字的乘积为 prod[n-k]。更新 prod 数组的方法是，每当进来一个数字 num 时，prod 数组新加一个1，然后对此时 prod 数组中每个数字都乘以 num，做个小优化，当 num 为1时，不需要乘，最后返回 prod[n-k] 即可，参见代码如下：

解法三：

class ProductOfNumbers {
 public:
     ProductOfNumbers() {}
    
     void add(int num) {
         prod.push_back(1);
         if (num == 1) return;
         for (int &a : prod) a *= num;
     }
    
     int getProduct(int k) {
         return prod[(int)prod.size() - k];
     }
    
 private:
     vector<int> prod;
 };

Github 同步地址:

#1352

参考资料：

https://leetcode.com/problems/product-of-the-last-k-numbers/

https://leetcode.com/problems/product-of-the-last-k-numbers/solutions/510265/c-prefix-array/

https://leetcode.com/problems/product-of-the-last-k-numbers/solutions/510260/java-c-python-prefix-product/

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~