腾讯音乐9月26日笔试
求大佬帮我看一下第二题(元素乘积尾部0大于x的子数组个数)解法哪里有什么问题
只能过20%，没有报时间复杂度错误
import java.util.*;
public class code2 {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型ArrayList
* @param x int整型
* @return int整型
*/
public int get_mod_2(int x) {
int res = 0;
while (x%2==0) {
res++;
x /= 2;
}
return res;
}
public int get_mod_5(int x) {
int res = 0;
while (x%5==0) {
res++;
x /= 5;
}
return res;
}
public int getSubarrayNum (ArrayList<Integer> a, int x) {
// write code here
long[][] cnt_arr = new long[2][a.size()]; // 记录因子有多少2 因子有多少5
for (int i = 0; i < a.size(); i++) {
cnt_arr[0][i] = get_mod_2(a.get(i));
cnt_arr[1][i] = get_mod_5(a.get(i));
}
int[] records = new int[a.size()]; // 以下标开始，存的数是区间的终止位置，区间内的数相乘结尾至少有x个0，且保证区间最短
for (int i = 0; i < a.size(); i++) {
records[i] = -1;
}
long record_2 = 0;
long record_5 = 0;
int begin_index = 0;
for (int end_index = 0; end_index < a.size(); end_index++) {
record_2 += cnt_arr[0][end_index];
record_5 += cnt_arr[1][end_index];
while (record_2 >= x && record_5>=x) {
records[begin_index] = end_index;
record_2 -= cnt_arr[0][begin_index];
record_5 -= cnt_arr[1][begin_index];
begin_index++;
}
}
int res = 0;
for (int i = 0; i < records.length; i++) {
if (records[i] == -1) break; // 当前位置为-1，表示后面区间所有的数相乘都不能得到末尾有两个0的数
res += ((a.size()-records[i]) % ((int)(Math.pow(10,9)+7))); // 当前位置开头的结果
}
return res;
}
} 
