给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
- 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
- 否则，div[i] = 0
- 返回 word 的可整除数组。
示例 1：
输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。示例 2：
输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。说明：
- 1 <= n <= 10^5
- word.length == n
- word 由数字 0 到 9 组成
- 1 <= m <= 10^9
思路
题目要求的是从字符串第一个数字开始，验证数字能否被给定的正整数m整除。很容易想到的方法是创建一个StringBuilder，遍历字符串的Character，依次加入StringBuilder，然后转化为数字，求余判断能否整除。提交运行发现会溢出，虽然word的最大长度为10^5，但是Long的最大值也才 9223372036854775807 共19位，直接求解行不通。
很自然地想到需要分治处理，比方说先在Long的范围内算，每次处理19位，然后记录余数，再接上后面的18位。但是感觉这样具体实现起来很别扭，实际上求余数的时候也没必要每次都从头开始。
因此，我们可以用每一位对m（它不超过10^9，在Integer 2147483647 的范围内）进行MOD运算，同时记录结果。如果为0，则将输出数组中的相应位置赋值为1，否则为0。然后将余数 remainder * 10加上下一位字符所示的数字，再进行MOD运算以此类推即可。
代码
/**
* @date 2024-03-07 9:27
*/
public class DivisibilityArray {
public int[] divisibilityArray(String word, int m) {
long remainder = 0;
int n = word.length();
int[] res = new int[n];
for (int i = 0; i < n; i++) {
remainder = (remainder * 10 + (word.charAt(i) - '0')) % m;
if (remainder == 0) {
res[i] = 1;
}
}
return res;
}
public static void main(String[] args) {
DivisibilityArray main = new DivisibilityArray();
String str = "1000000000100000000030199999999610000000009199999999079999999938299999999010000000009999999991100000000010000000001000000000100000000071999999992100000000010000000003099999999759999999951000000000100000000010000000001000000000822999999988269999999921000000000100000000010000000005999999995900999999991100000000069999999947445979999999641999999999059999999957999999993100000000080609999999868999999992599999999867999999993100000000";
int m = 1000000000;
main.divisibilityArray(str, m);
}
}
这里面有个小技巧，就是使用 Character - '0'来得到相应的数字，Character.getNumericValue考虑的情况比较多，这里用不到。同时需要注意，余数应使用long类型防止整数溢出。
性能
