前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Contest 176 - LeetCode 1352. Product of the Last K Numbers

Contest 176 - LeetCode 1352. Product of the Last K Numbers

作者头像
ShenduCC
发布2020-02-24 15:49:43
3170
发布2020-02-24 15:49:43
举报
文章被收录于专栏:算法修养

题目

题意:求一个数组的后k个数字的乘积,这个数组是不断动态增加的。

题解:由于数字可能为0,所以我们只要维护最后一个0 的位置pos 之后的所有数字的前缀乘积就可以了。如果k<pos 答案显然为0,如果k>pos那么答案就是s[len]/s[len-k]

代码语言:javascript
复制
class ProductOfNumbers {
public:
    long long int a[50005];
    long long int s[50005];
    int len;
    int last;
    ProductOfNumbers() {
        len=0;
        s[0]=1;
        last=-1;
    }
    
    void add(int num) {
        
        a[len++]=num;
        if(num==0)
        {
            last = len-1;
            s[last+1]=1;
        }
        else
            s[len]=s[len-1]*num;
    }
    
    int getProduct(int k) {
        
        if( last ==-1 ||len-k > last)
            return s[len]/s[len-k];
        else
            return 0;
        
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-02-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档