LeetCode-1352.最后K个数的乘积(Product of the Last K Numbers) 题解

16 February 2020

Leetcode-1352(力扣-1352)

Leetcode-1352(力扣-1352)

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

Adds the number num to the back of the current list of numbers.

2. 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.

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:

There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

题目描述

本题是一道设计题，本身逻辑比较简单。给出一个类，需要实现类中的2个方法：

add(int num) 向列表的尾部追加一个整数。
getProduct(int k) 计算列表倒数k个数的乘积。

个人题解1

class ProductOfNumbers:

    def __init__(self):
        self.total = 1
        self.lst = []			# 存储每次追加的整数
        self.lst_withoutz = []	# 保存前缀积

    def add(self, num: int) -> None:
        self.total *= (1 if num == 0 else num) # 计算前缀积
        self.lst.append(num)
        self.lst_withoutz.append(self.total)

    def getProduct(self, k: int) -> int:
        if self.lst[-k:].count(0) > 0:
            return 0
        if k == 1:
            return self.lst[-1]
        if k == len(self.lst_withoutz):
            return self.lst_withoutz[-1]
        return int(self.lst_withoutz[-1] / self.lst_withoutz[len(self.lst_withoutz) - k - 1])

个人题解1分析：

利用前缀积的方式来计算倒数k个数的乘积和。代码中的self.lst_withoutz用来保存前缀积，每次调用add方法，便进行一次计算。另外，为了不影响乘积的操作，如果遇到是0的情况，需要把0替换成1。最后在getProduct方法中，只需要将所有数的乘积除以倒数k个数之前的乘积，便是所求。所有数的乘积存在数组lst_withoutz的最后一个数，倒数k个数之前的乘积存储在数组的L-k-1的位置，L是数组的长度。

这种解法在数据量大的时候会超时。后来改进了见个人题解2

个人题解2

from collections import defaultdict


class ProductOfNumbers:

    def __init__(self):
        self.dic_lst = []  # 字典数组
        self.lst = []  # 存储每次追加的整数

    def add(self, num: int) -> None:
        self.lst.append(num)
        # 每次新增时，copy字典数组中最后一个字典，并且将新增的整数存入该字典中
        if len(self.dic_lst) == 0:
            dic = defaultdict(int)
            dic[num] += 1
            self.dic_lst.append(dic)
        else:
            dic = self.dic_lst[-1].copy()
            dic[num] += 1
            self.dic_lst.append(dic)

    def getProduct(self, k: int) -> int:
        # 获取字典中所有数的乘积
        def get_dic_product(dic_tmp):
            if dic_tmp[0] > 0:
                return 0
            num = 1
            for k, v in dic_tmp.items():
                if v <= 0:
                    continue
                num *= k ** dic_tmp[k]
            return num

        # 获取字典数组中尾部的字典，其中存储了当前所有的整数及出现的次数
        total_dic = self.dic_lst[-1].copy()
        if k == 1:
            return self.lst[-1]
        if k == len(self.lst):
            return get_dic_product(self.dic_lst[-1])

        # 获取字典数组中倒数第k-1个字典，其中存储数了当前除去倒数k个整数的所有整数及出现次数
        pre_dic = self.dic_lst[len(self.dic_lst) - k - 1]
        for k, v in pre_dic.items():
            total_dic[k] -= v
        return get_dic_product(total_dic)

个人题解分析2：

由于性能问题，考虑到用字典来做存储。每次新增一个整数时，会新建一个字典,存到字典数组dic_lst中。其中，新建的字典中的key是当前整数数组lst中的整数，value是该整数出现的次数。

在计算倒数k个乘积时，需要获取到2个字典：

# 获取字典数组中尾部的字典，其中存储了当前所有的整数及出现的次数
total_dic = self.dic_lst[-1].copy()
# 获取字典数组中倒数第k-1个字典，其中存储数了当前除去倒数k个整数的所有整数及出现次数
pre_dic = self.dic_lst[len(self.dic_lst) - k - 1]

之后将total_dic和pre_dic做一个差集，即可求得倒数k个数组成的字典，调用get_dic_product方法，即可求解。

LeetCode 4