算法leetcode

力扣1352-最后K个数的乘积

字数统计: 913字   |   阅读时长: 3分
, ,

摘要: 一个前缀和的变种问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

前缀和是力扣上非常常见的一个算法知识点，题非常多。在文章 【模板】前缀和与差分 中，我们介绍了前缀和与差分的算法原理和代码模板。在文章 前缀和问题分类汇总 中，我们详细梳理的力扣上的前缀和问题，共 44 道题。

本文我们看一个前缀和的变种问题，把加法改为乘法，也就是把前缀和改为前缀积，问题和解法有什么变化。

在 最大子数组乘积 中，我们处理过类似的子数组的乘积问题，两道题可以对比着看。

$1 题目

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

1
1. add(int num)

将数字 num 添加到当前数字列表的最后面。

1
2. getProduct(int k)

返回当前数字列表中，最后 k 个数字的乘积。
你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。

1
2
3
4
5
提示：

add 和 getProduct 两种操作加起来总共不会超过 40000 次。
0 <= num <= 100
1 <= k <= 40000

示例：

输入：
[“ProductOfNumbers”,”add”,”add”,”add”,”add”,”add”,”getProduct”,”getProduct”,”getProduct”,”add”,”getProduct”]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

输出：
[null,null,null,null,null,null,20,40,0,null,32]

解释：
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); // 返回 20 。最后 2 个数字的乘积是 5 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 5 4 = 40
productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 2 5 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32

$2 题解

算法1: 对数的前缀和

将前缀和的运算推广到乘积，如果有 prefix_product[i] := nums[0..i-1] 的乘积，那么区间 [i, j] 的乘积就是 prefix_product[j + 1] / prefix_product[i]

在实现时可以直接维护前缀积，也可以用对数的前缀和做个中转，防止前缀积的数值溢出，但是结果转回整数需要用四舍五入而不是下取整。

代码 (C++)

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
class ProductOfNumbers {
public:
    ProductOfNumbers() {
        n = 0;
        most_right_0 = -1;
        prefix_log_sum = vector<double>({0});
    }

    void add(int num) {
        if(num == 0)
        {
            most_right_0 = n;
            ++n;
            prefix_log_sum.push_back(prefix_log_sum.back());
        }
        else
        {
            ++n;
            prefix_log_sum.push_back(prefix_log_sum.back() + log2(num));
        }
    }

    int getProduct(int k) {
        if(most_right_0 >= n - k)
            return 0;
        else
            return round(pow(2, prefix_log_sum[n] - prefix_log_sum[n - k]));
    }

private:
    int n;
    int most_right_0;
    vector<double> prefix_log_sum;
};

算法2：前缀积

当然也可以直接在前缀和的基础上修改，加法改为乘法，减法改为除法。不处理前缀乘积的数值溢出问题。如果数据规模不大的话也是可以的。

代码 (C++)

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
class ProductOfNumbers {
public:
    ProductOfNumbers() {
        n = 0;
        most_right_0 = -1;
        prefix_product = vector<ll>({1});
    }

    void add(int num) {
        if(num == 0)
        {
            most_right_0 = n;
            ++n;
            prefix_product.push_back(1);
        }
        else
        {
            ++n;
            prefix_product.push_back(prefix_product.back() * num);
        }
    }

    int getProduct(int k) {
        if(most_right_0 >= n - k)
            return 0;
        else
        {
            return prefix_product[n] / prefix_product[n - k];
        }
    }

private:
    using ll = long long;

    int n;
    int most_right_0;
    vector<ll> prefix_product;
};
Share