更多精彩內(nèi)容，請(qǐng)關(guān)注【力扣簡(jiǎn)單題】。

題目

難度：★☆☆☆☆
類型：數(shù)組

題目

給定由若干 0 和 1 組成的數(shù)組 A。我們定義 N_i：從 A[0] 到 A[i] 的第 i 個(gè)子數(shù)組被解釋為一個(gè)二進(jìn)制數(shù)（從最高有效位到最低有效位）。

返回布爾值列表 answer，只有當(dāng) N_i 可以被 5 整除時(shí)，答案 answer[i] 為 true，否則為 false。

提示
1 <= A.length <= 30000
A[i] 為 0 或 1

示例

示例 1
輸入：[0,1,1]
輸出：[true,false,false]
解釋：
輸入數(shù)字為 0, 01, 011；也就是十進(jìn)制中的 0, 1, 3 。只有第一個(gè)數(shù)可以被 5 整除，因此 answer[0] 為真。

示例 2
輸入：[1,1,1]
輸出：[false,false,false]

示例 3
輸入：[0,1,1,1,1,1]
輸出：[true,false,false,false,true,false]

示例 4
輸入：[1,1,1,0,1]
輸出：[false,false,false,false,false]

解答

我們用寄存器s(i)記錄當(dāng)前A[0:i+1)子數(shù)組轉(zhuǎn)為十進(jìn)制后的值，存在遞推式：

s(i) = s(i-1) * 2 + A[i]

因此我們可以根據(jù)上一次的s計(jì)算當(dāng)前s，并且隨時(shí)判斷當(dāng)前s能否被5整除。

class Solution:
    def prefixesDivBy5(self, A):
        """
        :param A: List[int]
        :return: List[bool]
        """
        s = 0
        res = []
        for n in A:
            s = s * 2 + n
            res.append(s % 5 == 0)
        return res

如有疑問或建議，歡迎評(píng)論區(qū)留言~