一、题目
给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
示例1：
1
2
3
4
| 输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
|
示例2：
1
2
| 输入：[1,1,1]
输出：[false,false,false]
|
示例3：
1
2
| 输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
|
示例4：
1
2
| 输入：[1,1,1,0,1]
输出：[false,false,false,false,false]
|
提示：
1 ≤ A.length ≤ 30000A[i] 为 0 或 1
二、题解
模拟法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 题解：
对数组 [A[0], A[1], A[2]] 模拟一下这个过程：
第一个数N1：A[0]，然后对 5 去余判断是否为0
第二个数N2：A[0] * 2 + A[1]，然后对 5 去余判断是否为0
第三个数N3：A[0] * 4 + A[1] * 2 + A[2]，然后对 5 去余判断是否为0
我们可以发现 N(i) = N(i-1) * 2 + A[i-1]
考虑到数组 A 可能很长，如果每次都保留 N(i) 的值，则可能导致溢出。
但是因为只需要知道 N(i) 是否可以被 5 整除，因而我们可以每一轮只更新 N(i) % 5，结果不会影响，即
N(i) = (N(i-1) * 2 + A[i-1]) % 5
|
- 时间复杂度：O($n$)，其中 n 是数组 A 的长度。
- 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
| var prefixesDivBy5 = function(A) {
const ret = [];
let len = A.length;
let prefix = 0;
for (let i=0; i<len; i++) {
prefix = (prefix * 2 + A[i]) % 5;
ret.push(prefix === 0)
}
return ret
};
|
