LEETCODE 1352. Product of the Last K Numbers 解题思路分析

题目大意:

最后 K 个数的乘积

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

add(int num)

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

getProduct(int k)

  • 返回当前数字列表中,最后 k 个数字的乘积。
  • 你可以假设当前列表中始终 至少 包含 k 个数字。

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

示例:

解释:
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 

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1352

解题思路分析:

看到求连续区间乘积的题,我们应该想到使用前缀数组来解题。数组中下标为i的值代表从开始到第i位所有数的乘积,如果求最后k个数的乘积时,答案应该等于所有数乘积除以最后k个数以外数字的乘积。这与之前讲过的前缀和数组的解题思路非常相似。比如:

[1,2,3,4]

它的前缀乘积数组应该是:

int[] pre =[1,2,6,24]

如果我们求最后2位的乘积应该是pre[3] / pre[1] = 24 / 2 = 12

但是,乘法必须考虑到数字0的情况,如果前面某一位上的数字是0,那么他之后的乘积都是0,这样我们计算后k个数的乘积时就无法得到争取的结果,比如:

[2,4,0,6,8]

它的前缀乘积数组应该是:

[2,8,0,0,0]

这时我们如果求最后两位的乘积,显然是无法通过前缀数组求解的。因此使用前缀数组解决乘积问题时,我们需要做出一些变化,当出现数字0时,我们清空数组,数组中只保存最后不为0部分的乘积,凡是k大于前缀数组长度时我们可以返回0,反之可以按照上面的方式求解。

实现代码:

// 定义前缀乘积数组
// 由于数组长度未知,本体使用List类来代替
List<Integer> list = new ArrayList<>();
public ProductOfNumbers() {

}

public void add(int num) {
    // 如果当前数字为0,清空list
    if(num==0){
        list.clear();
        return;
    }
    // 如果list中元素个数大于0,
    if(list.size()>0){
        // 当前的前缀乘积为前一个前缀乘积乘以当前数字
        list.add(list.get(list.size()-1)*num);
    }else{ // 如果list为空
        // 将当前数字加入list
        list.add(num);
    }
}

public int getProduct(int k) {
    // 如果k大于list中元素个数大小,说明最后k个长度的元素中包含0,
    // 返回0
    if(k>list.size()) return 0;
    // 如果k等于list元素个数,那么返回list中最后一个元素
    if(k==list.size()) return list.get(list.size()-1);
    // 反之返回list中最后一个值除以最后k个值以外数字的乘积的商
    return list.get(list.size()-1) / list.get(list.size()-k-1);
}

本题解法执行时间为13ms。

Runtime: 13 ms, faster than 98.99% of Java online submissions for Product of the Last K Numbers.

Memory Usage: 54.4 MB, less than 100.00% of Java online submissions for Product of the Last K Numbers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1352-product-of-the-last-k-numbers-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。