找出字符串的可整除数组

You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.

The divisibility array div of word is an integer array of length n such that:

• div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, or
• div[i] = 0 otherwise.

Return the divisibility array of word.

 

Example 1:

Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".

Example 2:

Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".

 

Constraints:

• 1 <= n <= 105
• word.length == n
• word consists of digits from 0 to 9
• 1 <= m <= 109

/*
 * 题目思路：
 * 1. 使用 Java Stream 处理字符串 word 的每个字符，逐个累加形成前缀数字。
 * 2. 对每个前缀数字检查是否能被 m 整除。
 * 3. 如果能被整除，则在结果数组的相应位置标记 1，否则标记 0。
 */
import java.util.stream.IntStream;

public class Solution {
    public int[] divisibilityArray(String word, int m) {
        int n = word.length();
        final long[] num = {0};
        return IntStream.range(0, n).map(i -> {
            num[0] = num[0] * 10 + (word.charAt(i) - '0');
            int result = (num[0] % m == 0) ? 1 : 0;
            num[0] %= m; // 避免溢出，保留余数
            return result;
        }).toArray();
    }
}

这道题要求对于字符串 'word' 中的每个前缀，判断其转换成整数后是否能被 'm' 整除。直接计算每个前缀的整数值会非常耗时，尤其是前缀很长的情况。因此，题解采用了模运算的性质来逐步构建每个前缀的模 'm' 值。通过维护一个当前值 'cur'，每次读取一个新的字符，都将 'cur' 更新为 '(cur * 10 + 当前字符值) % m'。这样，'cur' 始终保持为当前前缀对 'm' 的模。如果 'cur' 为0，则说明当前前缀可以被 'm' 整除，反之则不能。这种方法避免了直接计算大数的除法，是一种时间效率和空间效率较高的解决方案。

O(n)

O(1)