给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于
的连续子数组数量。
答案可能太大，请将答案对
取模再返回。
数组元素、均为不超过
的正整数。
[编程题]连续子数组数量
- 热度指数：1021 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例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)
先计算出每个数可以拆分成多少个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)
说说我的思路：
首先要知道一个知识点，末尾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)
前缀和
由于累乘结果末尾零的数量取决于和
这两个因子数量的较小值，因此预处理出
和
。其中
表示
中因子
的个数；
表示
中因子
的个数。
然后枚举数组的左端点，我们需要找到一个
，使子数组
中元素
因子的个数和
因子的个数之和不小于
，这样一来
就都可以在数组左端点为
时作为数组的右端点，一共可以贡献
个子数组。
只需要把
和
变为前缀和数组，形成单调性，就可以用二分查找来确定
的位置。
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)
// 获取一个数中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)
问题信息
通过挑战的用户
-
2023-03-03 15:13:54
-
2023-03-01 08:38:39
-
2023-02-25 11:26:52 -
2023-02-23 20:38:45
-
2023-02-17 22:31:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
