当前位置:网站首页>【Leetcode】1352. 最后 K 个数的乘积
【Leetcode】1352. 最后 K 个数的乘积
2022-07-05 04:46:00 【wangzirui32】
博文作者 wangzirui32
喜欢的可以 点赞 收藏 关注哦~~
本文首发于CSDN,未经许可禁止转载
1. 题目描述
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/product-of-the-last-k-numbers/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题思路
这道题有点难度,我们不能记录每次add
添加的数字,这样每次getProduct
都要计算乘积,耗时较大(我用此方法编写代码显示超时),于是,我们需要换一种思路:我们可不可以每次add
时顺带把乘积计算完毕存入列表呢?可以,假设我们输入了如下长度为4的列表:
索引 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
数值 | a a a | b b b | c c c | d d d |
然后,我们把它转化为一个新列表:
索引 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
数值 | a a a | a b ab ab | a b c abc abc | a b c d abcd abcd |
可以看到,数值依次成为了ab
, abc
等的乘积,设我们需要计算后K个数的乘积(假设 k = 2 k=2 k=2),等价于求 c d cd cd的乘积,就是 a b c d / a b = c d abcd / ab = cd abcd/ab=cd,也就是索引倒数第一除以倒数第三,引入 K K K即可表达为:
r e s u l t = n u m s [ − 1 ] / n u m s [ − k − 1 ] result = nums[-1] / nums[-k-1] result=nums[−1]/nums[−k−1]
3. 代码实现
Code:
class ProductOfNumbers:
def __init__(self):
self.product_list = [1] # 初始值为1
def add(self, num):
if num == 0: # 如果为0 在此之后的乘积均为0 所以重置列表
self.product_list = [1]
else:
# 与列表最后一项相乘 即可出现 a ab abc 一类的列表
self.product_list.append(num * self.product_list[-1])
def getProduct(self, k):
if k >= len(self.product_list):
# k大于长度返回0
return 0
else:
# result = nums[-1] / nums[-k-1]
return self.product_list[-1] / self.product_list[-k-1]
4. 最终结果
好了,今天的课程就到这里,我是wangzirui32,喜欢的可以点个收藏和关注,我们下次再见!
边栏推荐
- Séparation et combinaison de la construction du système qualité
- Mxnet imports various libcudarts * so、 libcuda*. So not found
- XSS injection
- 包 类 包的作用域
- The remainder operation is a hash function
- [groovy] closure (closure parameter list rule | default parameter list | do not receive parameters | receive custom parameters)
- English topic assignment (26)
- [crampon game] MC tutorial - first day of survival
- 直播预告 | 容器服务 ACK 弹性预测最佳实践
- Discussion on the dimension of confrontation subspace
猜你喜欢
Solutions and answers for the 2021 Shenzhen cup
【acwing】240. food chain
10 programming habits that web developers should develop
托管式服务网络:云原生时代的应用体系架构进化
[groovy] closure (Introduction to closure class closure | this, owner, delegate member assignment and source code analysis)
[groovy] closure (closure as function parameter | code example)
2022 U.S. college students' mathematical modeling e problem ideas / 2022 U.S. game e problem analysis
Introduce Hamming distance and calculation examples
Looking at Chinese science and technology from the Winter Olympics: what is the mystery of the high-speed camera that the whole people thank?
Setting up redis cluster cluster under Windows
随机推荐
Qt蓝牙:搜索蓝牙设备的类——QBluetoothDeviceDiscoveryAgent
Number theoretic function and its summation to be updated
Reading and visualization of DICOM, MHD and raw files in medical imaging
直播预告 | 容器服务 ACK 弹性预测最佳实践
Emlog博客主题模板源码简约好看响应式
SQLServer 存储过程传递数组参数
数论函数及其求和 待更新
首席信息官如何利用业务分析构建业务价值?
Basic analysis of IIC SPI protocol
The first topic of ape Anthropology
Cookie learning diary 1
Construction d'un Cluster redis sous Windows
Thinking of 2022 American College Students' mathematical modeling competition
次小生成树
SQL set operation
Neural networks and deep learning Chapter 5: convolutional neural networks reading questions
2022 U.S. college students' mathematical modeling e problem ideas / 2022 U.S. game e problem analysis
2022-2028 global and Chinese equipment as a Service Market Research Report
Neural network and deep learning Chapter 1: introduction reading questions
Solutions and answers for the 2021 Shenzhen cup