这是小川的第379次更新，第407篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第241题（顺位题号是1018）。给定0和1的数组A，考虑
N_i
：从
A[0]
到
A[i]
的第
i
个子数组被解释为二进制数（从最高有效位到最低有效位）。
返回布尔值
answer
列表，当且仅当
N_i
可被5整除时，
answer[i]
为
true
。
例如：
输入：[0,1,1]
输出：[true，false，false]
说明：二进制输入数字为
,
01
011
，转为十进制数，分别为0,1和3。只有第一个数字可以被5整除，所以
answer[0]
true
输入：[1,1,1]
输出：[false，false，false]
输入：[0,1,1,1,1,1]
输出：[true，false，false，false，true，false]
输入：[1,1,1,0,1]
输出：[false，false，false，false，false]
注意：
- 1 <= A.length <= 30000
-
A[i]
02 解题
题目的意思是
A
中都是二进制位的0和1，依次从左到右，判断二进制组成的十进制数能否被5整除，将每次的判断结果存入
List
按照常规的操作，循环A中的元素，组成一个二进制字符串，再转成十进制数，再对5取余，将判断结果存入
List
中，但是有个问题需要考虑，
A
的长度上限是30000，如果组合成的二进制字符串长度过长，是否还能被转成整数？答案存疑，那我们需要换另外一种思路来解决问题了。
结合例子来看，
[1,1,1,0,1]
，从左往右看：
第一次计算，二进制数为
1
，转为十进制为1，
1%5
=1。
第二次计算，二进制数为
11
，转为十进制为3，
(1*2+1)%5
= 3%5 =3。
第三次计算，二进制数为
111
，转为十进制为7，
(3*2+1)%5
= 7%5 =2。
第四次计算，二进制数为
1110
，转为十进制为14，
(2*2+0)%5
= 4%5 = 14%5 =4。
第五次计算，二进制数为
11101
，转为十进制为29，
(4*2+1)%5
= 9%5 = 29%5 =4。
从例子中可以看到，新的二进制数是在前一次二进制数的基础上左移一位得到的，即
num[i+1] = (A[i]<<1) + A[i+1]
，
A[i]
为前一次的十进制整数，
A[i+1]
为在前一次二进制数尾部新加的0或1，题目只是需要我们判断每次新组成的二进制数能否被5整除，我们可以利用前一次取余的结果左移，因为其中能被整除的部分是不太需要关心的，这样可以避免数字过大超出范围的风险。
public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> answer = new ArrayList<Boolean>();
int num = 0;
for (int i=0; i<A.length; i++) {
// 写成 num = (num<<1) + A[i]; 也是一样的效果
num = num*2 + A[i];
num %= 5;
answer.add(num == 0);
}
return answer;
}
小结
算法专题目前已连续日更超过七个月，算法题文章247+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！