【Leetcode】1352. Product of the last K numbers

Bowen author wangzirui32
Like can give the thumbs-up Collection Pay attention to ~~
This article was first published in CSDN, Reprint is prohibited without permission

1. Title Description

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/product-of-the-last-k-numbers/
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Their thinking

This problem is a little difficult , We can't record every time add Added number , So every time getProduct We have to calculate the product , Time consuming （ I use this method to write code to display timeout ）, therefore , We need to change our thinking ： Can we each time add By the way, calculate the product and store it in the list ？ Sure , Suppose we enter the following length 4 A list of ：

Indexes	0	1	2	3
The number	$a$	$b$	$c$	$d$

then , We turn it into a new list ：

Indexes	0	1	2	3
The number	$a$	$ab$	$abc$	$abcd$

You can see , The values in turn become ab, abc Equal product , Suppose we need to calculate K The product of numbers （ hypothesis $k=2$）, It's equivalent to asking for $cd$ The product of the , Namely $abcd/ab=cd$, That is, the index is divided by the penultimate third , introduce $K$ It can be expressed as ：
$$result=nums[-1]/nums[-k-1]$$

3. Code implementation

Code：

class ProductOfNumbers:
    def __init__(self):
        self.product_list = [1]  #  The initial value is 1

    def add(self, num):
        if num == 0:     #  If 0  The products after that are 0  So reset the list 
        	self.product_list = [1]
        else:
        	#  Multiply by the last item in the list   Can appear  a ab abc  A list of classes 
        	self.product_list.append(num * self.product_list[-1])

    def getProduct(self, k):
        if k >= len(self.product_list):
        	# k Greater than length returns 0
        	return 0
        else:
        	# result = nums[-1] / nums[-k-1] 
        	return self.product_list[-1] / self.product_list[-k-1]

4. final result

Okay , That's all for today's lesson , I am a wangzirui32, You can collect and pay attention to what you like , See you next time ！