连续子数组数量

[编程题]连续子数组数量

热度指数：1029 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于 $x$ 的连续子数组数量。

答案可能太大，请将答案对 $10^9+7$ 取模再返回。

数组长度不超过 $10^5$ 。

数组元素、 $x$ 均为不超过 $10^9$ 的正整数。

示例1

输入

[5,2,3,50,4],2

输出

说明

共有以下6个合法连续子数组：
[5,2,3,50]，乘积为1500，末尾有2个零。
[5,2,3,50,4]，乘积为6000，末尾有3个零。
[2,3,50]，乘积为300，末尾有2个零。
[2,3,50,4]，乘积为1200，末尾有2个零。
[3,50,4]，乘积为600，末尾有2个零。
[50,4]，乘积为200，末尾有2个零。

算法知识视频讲解

Java

Sumxmq

先计算出每个数可以拆分成多少个5和2的乘积。然后以每一个数为起点，往后遍历，看遍历到什么位置，可以满足题目的条件，这部分可以用滑动窗口的知识来优化。

import java.util.*;
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型ArrayList
     * @param x int整型
     * @return int整型
     */
    static final int MOD = 1000000007;
    public int getSubarrayNum (ArrayList<Integer> a, int x) {
        int n = a.size();
        int[] five = new int[n];
        int[] two = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++){
            int val = a.get(i);
            while (val % 5 == 0 && val >= 5){
                five[i]++;
                val /= 5;
            }
            val = a.get(i);
            while (val % 2 == 0 && val >= 2){
                two[i]++;
                val /= 2;
            }
        }
        int r = 0, val1 = five[0], val2 = two[0];
        for (int l = 0; l < n; l++){
            while (r < n - 1 && Math.min(val1, val2) < x){
                r++;
                val1 += five[r];
                val2 += two[r];
            }
            if (Math.min(val1, val2) >= x) ans += (n - r);
            ans %= MOD;
            val1 -= five[l];
            val2 -= two[l];
        }
        return ans;
    }
}

发表于 2023-03-12 16:15:19 回复(0)