1018-可被5整除的二进制前缀_综合

题目描述

给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。

返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。输入：[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] 为 0 或 1

解题思路

暴力破解

如已知A=[0,1,0]，变换 B=['0', '1', '0']，变换C=['0', '01', '010']，之后将C中每个值进行判断即可。

优点：简单直接，不存在思路上的困难；
缺点：解法不论是在空间还是时间上不占优；

class Solution:def prefixesDivBy5(self, A: List[int]) -> List[bool]:List = A	# 初始化Liststr_A = [str(i) for i in A]	# 将A转换成字符串数组if A[0] == 0:	# 判断第一个数字是否符合List[0] = Trueelse: List[0] = Falseif len(str_A) == 1:return Listelse:str_res = str_A	# str_res初始化str_res[0] = str_A[0]for j in range(1, len(str_A)):str_res[j] = str_res[j-1] + str_A[j]int_res = int(str_res[j],2)if int_res % 5 == 0:List[j] = Trueelse: List[j] = Falsereturn List

数学分析

在进行代码优化前，我们先从数学角度进行分析，会得出如下结论：
设\(N_i\)为A中从下标0到下标i构成的二进制数，则有：

\(N_0 = A[0]\)
\(N_i = N_{i-1} *2 + A[i], i>0\)(这是二进制的左移性质)

所以，我们可以将上面“数字-字符串-数字”的过程变成上面递推公式的计算。但是这个思路存在的问题：考虑到数组A可能很长，如果每次都保留\(N_i\)的值，则可能导致溢出。

解决方案：\(M_i=N_i mod 5=(N_{i-1} *2 + A[i])mod5=(M_{i-1} *2 + A[i])mod5\)，即可以用余数代替N完成运算。

在上面思路的基础上，代码如下：

class Solution:def prefixesDivBy5(self, A: List[int]) -> List[bool]:ans = list()prefix = 0for num in A:prefix = ((prefix << 1) + num) % 5ans.append(prefix == 0)return ans

prefix初始化为0，0<<1左移的结果仍然是0。

思路总结

本题侧重于数学分析，如果分析不到位，会出现两种情况：

使用\(N_{i-1}*2\)去递推得到\(N_i\)的值，最后因为数值过大造成溢出；
当作字符串处理(暴力破解法)，尽管没有溢出问题，但是性能不佳。