专栏首页算法修养Contest 176 - LeetCode 1352. Product of the Last K Numbers

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

题目

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

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

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);
 */

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HYSBZ 3676 回文串 (回文树)

    3676: [Apio2014]回文串 Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 1680  Solve...

    ShenduCC
  • HYSBZ 2160 拉拉队排练(回文树)

    2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

    ShenduCC
  • HYSBZ 2565 最长双回文串 (回文树)

    2565: 最长双回文串 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1377  Solved: 714 ...

    ShenduCC
  • 算法细节系列(19):广度搜索优先

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【统计难题】【HDU - 1251】【map打表或字典树】【字典树模板】

    题意:题目为中文题,这里不再过多阐述。 思路1:可以在读入单词表的过程中将单词分解,用map将它一 一记录 思路2:利用字典树,这个方法较快些,下面代码中会...

    _DIY
  • HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

    题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数

    用户2965768
  • LeetCode 594. 最长和谐子序列(map)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-harmonious-subseque...

    Michael阿明
  • C++上机考试试题解析

    慕白
  • LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium

    题目: Given a string, find the length of the longest substring without repeating c...

    CloudDeveloper
  • hdu1063

    @坤的

扫码关注云+社区

领取腾讯云代金券