首页 > 试题广场 >

连续子数组数量

[编程题]连续子数组数量
  • 热度指数：1022 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于x的连续子数组数量。
答案可能太大，请将答案对取模再返回。

数组长度不超过。
数组元素、x均为不超过的正整数。
示例1

输入

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

输出

6

说明

共有以下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个零。
算法知识视频讲解
添加回答
澪语头像 澪语 
class Solution {
public:
    int mod = 1e9 + 7;
    int n = 0;
    void func(vector<int>& a, vector<vector<int>>& arr) {
        for (int i = 0; i < n; ++i) {
            int temp = a[i];
            while (temp > 0 && temp % 2 == 0) {
                arr[i][0]++;
                temp /= 2;
            }
            temp = a[i];
            while (temp > 0 && temp % 5 == 0) {
                arr[i][1]++;
                temp /= 5;
            }
        }
    }
    int get_ans(vector<vector<int>>& arr, int x) {
        long long ans = 0;
        int two_num = 0, five_num = 0;
        int l = 0, r = 0;
        while (r < n) {
            two_num += arr[r][0];
            five_num += arr[r][1];
            while (min(two_num, five_num) >= x) {
                ans += n - r;
                two_num -= arr[l][0];
                five_num -= arr[l][1];
                ++l;
            }
            ++r;
        }
        return ans % mod;
    }
    int getSubarrayNum(vector<int>& a, int x) {
        n = a.size();
        vector<vector<int>> arr(n, vector<int> (2));
        func(a, arr);
        return get_ans(arr, x);
    }
};
乘积末尾0的数量取决于乘积中因子2和因子5的最小值。 所以，要解决这个问题，我们可以先计算一下每个元素包含几个因子2和因子5，并用一个数组arr记录下来。 之后，再用双指针遍历arr数组，当累计的因子数量中的较小值大于等于x时，连续子数组乘积末尾0的数量必然大于等于x，此时进行下标计算即可求出以指针l为起始位置的所有连续子数组的数量。
发表于 2022-09-29 19:39:36 回复(3)
Java
Sumxmq头像 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)
扬蓬蒿头像 扬蓬蒿
为了避免大量的乘法运算，通过计算子数组的 2 因子和 5 因子的数目确定它末尾是否有 x 个零，再通过滑动窗口确定子数组的选择。

如果想加速，可以事先计算好每个数字的 2 因子和 5 因子个数，由于使用滑动窗口，每个数字的因子最多计算两次，这里就没有选择优化。 
import java.util.*;
public class Solution {
    final static int MOD = (int) 1e9 + 7;

    public int getSubarrayNum(ArrayList a, int x) {
        // 双指针
        int left, right;
        int ans = 0;
        left = right = 0;
        int[] current = new int[2]; // 0 位记录 2 的因子数量，1 位记录 5 的因子数量
        for (; right < a.size(); right++) {
            int num = a.get(right);
            current[0] += getFactorCount(num, 2);
            current[1] += getFactorCount(num, 5);
            while (Math.min(current[0], current[1]) >= x) {
                ans =  (ans + a.size() - right) % MOD; // 以 left 开头，以 right 以及大于 right 结尾都符合要求
                // 删除 left 的数
                num = a.get(left);
                current[0] -= getFactorCount(num, 2);
                current[1] -= getFactorCount(num, 5);
                left++;
            }
        }
        return ans;
    }
    // 计算 x 分解因子后，有多少个 f
    private int getFactorCount(int x, int f) {
        int count = 0;
        while (x % f == 0) {
            count++;
            x /= f;
        }
        return count;
    }
}
编辑于 2023-04-28 14:08:35 回复(0)
牛客42554552号头像 牛客42554552号
说说我的思路：
首先要知道一个知识点，末尾0的数量取决于所有因子中数量较小的2的数量和5的数量
我的思路是前缀和+二分
先预处理出2和5的数量，然后枚举连续子数组的起点，然后二分一下终点，加一下较小的就好
上代码： 
class Solution {
public:
    const int N = 1e9 + 7;
    int getSubarrayNum(vector<int>& a, int x) {
        vector<int> sum2(a.size() + 1);
        vector<int> sum5(a.size() + 1);
         
                //预处理2和5的数量
        for (int i = 0; i < a.size(); ++ i) {
            while (a[i] % 2 == 0) {
                a[i] /= 2;
                sum2[i + 1] ++;
            }
            while (a[i] % 5 == 0) {
                a[i] /= 5;
                sum5[i + 1] ++;
            }
            if (i) sum2[i + 1] += sum2[i], sum5[i + 1] += sum5[i];
        }
         
        int ans = 0;
        for (int i = 1; i <= a.size(); ++ i) { //枚举起始位置
            auto p = lower_bound(sum2.begin(), sum2.end(), sum2[i - 1] + x);
            auto q = lower_bound(sum5.begin(), sum5.end(), sum5[i - 1] + x);
            if (p == sum2.end()&nbs***bsp;q == sum5.end()) break;
            ans += min(sum2.end() - p, sum5.end() - q);  //一旦满足，后面的都满足
            ans %= N;
        }
        return ans;
    }
};


发表于 2022-11-01 17:52:03 回复(1)
C/C++
pein531头像 pein531

前缀和

由于累乘结果末尾零的数量取决于和这两个因子数量的较小值，因此预处理出和。其中表示中因子的个数；表示中因子的个数。
然后枚举数组的左端点，我们需要找到一个，使子数组中元素因子的个数和因子的个数之和不小于，这样一来就都可以在数组左端点为时作为数组的右端点，一共可以贡献个子数组。

只需要把和变为前缀和数组，形成单调性，就可以用二分查找来确定的位置。 
typedef long long LL;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param x int整型 
     * @return int整型
     */
    int getSubarrayNum(vector<int>& a, int x) {
        // write code here
        int n = a.size();
        vector<LL> cnt2(n), cnt5(n);
        for(int i = 0; i < n; i++) {
            cnt2[i] = (i? cnt2[i - 1]: 0) + count(a[i], 2);
            cnt5[i] = (i? cnt5[i - 1]: 0) + count(a[i], 5);
        }
        LL ans = 0;
        for(int left = 0; left < n; left++) {
            int j2 = bisect_left(cnt2, left, n - 1, (left? cnt2[left - 1]: 0) + x);
            int j5 = bisect_left(cnt5, left, n - 1, (left? cnt5[left - 1]: 0) + x);
            if(j2 == n || j5 == n) continue;    // 2和5两种因子缺一不可
            int right = max(j2, j5);
            ans = (ans + n - right) % MOD;
        }
        return ans;
    }

private:
    const int MOD = 1e9 + 7;
    int count(int x, int y) {
        int res = 0;
        while(x % y == 0) {
            res++;
            x /= y;
        }
        return res;
    }

    int windowSum(vector<int>& s, int left, int right) {
        return s[right] - (left? s[left - 1]: 0);
    }

    int bisect_left(vector<LL>& nums, int left, int right, LL target) {
        int index = right + 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] >= target) {
                index = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return index;
    }
};

编辑于 2023-02-02 17:49:43 回复(0)
想回学校的退堂鼓鼓手在找内推头像 想回学校的退堂鼓鼓手在找内推
golang 
前缀和 + 双指针 + 因子2和5的最小数量 
package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param a int整型一维数组 
 * @param x int整型 
 * @return int整型
*/
func getSubarrayNum( a []int ,  x int ) int {
    // write code here
    // 前缀和 + 2 * 5 + 双指针
    ans := 0
    n := len(a)
    dp := make([][]int, n)
    for i := range dp{
        dp[i] = make([]int , 2)
        dp[i][0] , dp[i][1] = getZero(a[i])
    }
    pre := make([][]int, n + 1)
    for i := range pre{
        pre[i] = make([]int, 2)
    }
    for i := 1 ; i <= n ; i++{
        pre[i][0] = pre[i - 1][0] + dp[i - 1][0]
        pre[i][1] = pre[i - 1][1] + dp[i - 1][1]
    }
    p := 0
    q := 0
    for q <= n{
        if (pre[q][0] - pre[p][0]) >= x && (pre[q][1] - pre[p][1]) >= x{
            ans += (n - q + 1)
            p += 1
        }else{
            q += 1
        }
    }
    return ans
}

func getZero(x int)(int, int){
    count2 := 0
    count5 := 0
    for {
        if x % 2 == 0{
            count2 += 1
            x /= 2
        }else if x % 5 == 0{
            count5 += 1
            x /= 5
        }else{
            break
        }
    }
    return count2, count5
}

发表于 2023-04-18 18:37:23 回复(0)
永恒钻石1头像 永恒钻石1 
// 获取一个数中2和5的数量
// 返回{2的数量，5的数量}
vector<int> Get5And2(double num) {
    int n = num, cnt_2 = 0, cnt_5 = 0;
    while(n % 2 == 0) {
        n = n / 2;
        cnt_2++;
    }
    n = num;
    while(n % 5 == 0) {
        n = n / 5;
        cnt_5++;
    }
    return {cnt_2, cnt_5};
}
const int mod = pow(10, 9) + 7;
int getSubarrayNum(vector<int>& a, int x) {
    // write code here
    int cnt = 0;
    int sz = a.size();
    vector<vector<int>> arr(2, vector<int>(2, 0));
    vector<vector<int>> all_5and2(sz, vector<int>(2, 0));
    // 求得每个元素的2和5的数量
    for(int i = 0; i < sz; i++) {
        all_5and2[i] = Get5And2(a[i]);
    }
    // 遍历所有组合，用取余减小使用的二维数组的大小
    for(int i = 0; i < sz; i++) {
        arr[i % 2] = all_5and2[i]; 
        for(int j = i + 1; j < sz; j++) {
            int jmod2 = j % 2, j_1mod2 = (j - 1) % 2;
            arr[jmod2] = all_5and2[j];
            arr[jmod2][0] += arr[j_1mod2][0];
            arr[jmod2][1] += arr[j_1mod2][1];
            // 找到了min(num2, num5)>=x的组合
            // 同一行剩下的组合也一定会符合要求
            // 所以直接加上剩余组合数，并且break结束内循环
            if(min(arr[jmod2][0], arr[jmod2][1]) >= x) {
                cnt = (cnt + (sz - j)) % mod;
                break;
            }
        }
    }
    return cnt;
}
发表于 2023-04-16 17:35:10 回复(0)
这辈子无了头像 这辈子无了

解题思路：前缀和

int getSubarrayNum(vector<int>& a, int x) {
        // write code here
        int n = a.size();
        vector<int> two(n + 1, 0), five(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int t = a[i - 1];
            if (t & 1) {
                two[i] = two[i - 1];
            }else {
                int cnt = 0;
                while (t && t % 2 == 0) {
                    cnt++;
                    t /= 2;
                }
                two[i] = two[i - 1] + cnt;
            }
        }

        for (int i = 1; i <= n; i++) {
            int t = a[i - 1];
            if (t % 5 != 0) {
                five[i] = five[i - 1];
            }else {
                int cnt = 0;
                while (t && t % 5 == 0) {
                    cnt++;
                    t /= 5;
                }
                five[i] = five[i - 1] + cnt;
            }
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (min(two[j] - two[i - 1], five[j] - five[i - 1]) >= x) {
                    ans = (ans + n - j + 1) % 1000000007;
                    break;
                }
            }
        }
        return ans;
    }
};
发表于 2022-11-08 10:32:42 回复(0)
提交观点

问题信息

上传者：小小
难度：
8条回答 4026浏览

热门推荐

通过挑战的用户

相关试题

连续子数组数量

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号