算法练习——可被 5 整除的二进制前缀

2021年1月14日LeetCode每日一题为1018. 可被 5 整除的二进制前缀,这道题非常简单,唯一要注意的地方就是溢出问题。因为其是二进制,我们用一个数来记录当前总值就可以,每一次将这个总值向左移一位再加上当前下标的二进制值即可实现累加值。但是仅仅这样是不够的,因为累加到后面总是会溢出,因为数组A的长度在30000以内,这时就要想想是不是可以不全加起来也可以解答,就要用到数学上的一点小技巧了,我们对每次的结果进行取余,并且只需要记住这个余数,继续执行累加即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> ans = new ArrayList<Boolean>();
int t = 0;
for (int value : A) {
t = ((t << 1) + value) % 5;
ans.add(t == 0);
}
return ans;
}
}

这种题目通常是考验溢出问题的处理,只要会一点位运算和除法相关的技巧都不是什么难题。算法就是这样,与数学存在着微妙的关系,所以数学的基础也是非常重要的,它永远是一个可选项,但对专门研究算法的人来说就是必修课了。