可被5整除的二进制前缀

发表于
本文字数： 777 阅读时长 ≈ 1 分钟

LeetCode每日一题，1018. Binary Prefix Divisible By 5

先看题目描述

saoEtJ.png

大意就是给定一个只包含 0 和 1 的数组 A，让我们返回一个相同长度的布尔数组 answer，answer[i] 的值为 true 当且仅当 A[0] 到 A[i] 构成的二进制数可被 5 整除

算法和思路

这题比较简单，我们从头到尾遍历 A 数组，用一个变量 cur 保存当前的二进制前缀数，当遍历到 A[i] 时，若当前保存的二进制前缀数可被 5 整除，则令 res[i] = true，否则为 false。考虑到数组 A 可能很长，若用 cur 保存当前的二进制前缀数的话，可能导致溢出，于是改为用 cur 保存当前的二进制前缀数对 5 的余数，然后每次判断 cur 是否为 0 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> res = new ArrayList<>();
        int cur = 0;
        for (int a : A) {
            cur = (cur * 2 + a) % 5;
            if (cur == 0) {
                res.add(true);
            } else {
                res.add(false);
            }
        }
        return res;
    }
}