阿里4.12笔试第三题

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

String s = scan.nextLine();

char[] c = s.toCharArray();

int sum = 0;

for (int i = 0; i < c.length; i++) {

sum += c[i] - '0';

}

//总体思想为保证最后一位为0或5，所有位相加是3的倍数

//因此问题转化为先求出整个数组的所有位的数之和并%3，假设等于k，则后面需要找子数组之和%3也等于k的个数

sum %= 3;

//dpk[i]表示以第i个数字为结尾的连续子数组的和%3等于k的个数

int[] dp0 = new int[c.length];

dp0[0] = (c[0] - '0') % 3 == 0 ? 1 : 0;

int[] dp1 = new int[c.length];

dp1[0] = (c[0] - '0') % 3 == 1 ? 1 : 0;

int[] dp2 = new int[c.length];

dp2[0] = (c[0] - '0') % 3 == 2 ? 1 : 0;

for (int i = 1; i < c.length; i++) {

int a = (c[i] - '0') % 3;

if(a == 0) {//当前数字%3等于0

dp0[i] = dp0[i - 1] + 1;//当前位拼接到前面，有dp0[i - 1]个子数组，或者不和前面拼接，自己为1个

dp1[i] = dp1[i - 1];

dp2[i] = dp2[i - 1];

} else if(a == 1) {

dp0[i] = dp2[i - 1];

dp1[i] = dp0[i - 1] + 1;

dp2[i] = dp1[i - 1];

} else {

dp0[i] = dp1[i - 1];

dp1[i] = dp2[i - 1];

dp2[i] = dp0[i - 1] + 1;

}

}

//如果删除的子数组包含最后一位，则前缀和%3等于0且以0或5为结尾的前缀才满足要求

int preSum = 0;

int last = 0;//删除的子数组包含最后一位时的子数组个数

for (int i = 0; i < c.length - 1; i++) {

preSum += c[i] - '0';

if(c[i] == '0' || c[i] == '5') {

if(preSum % 3 == 0) last++;

}

}

if(c[c.length - 1] == '0' || c[c.length - 1] == '5') {//如果原数组最后一位为0或5，就是dp数组的前n-1个元素之和加上last

if(sum == 0) System.out.println(getSum(dp0) + last);

else if(sum == 1) System.out.println(getSum(dp1) + last);

else System.out.println(getSum(dp2) + last);

return;

}

//如果原数组最后一位不是0或5，则直接输出last

System.out.println(last);

}

public static long getSum(int[] arr) {

long ans = 0;

for (int i = 0; i < arr.length - 1; i++) {

ans += arr[i];

}

return ans;

}

}