本文主要是介绍1018. Binary Prefix Divisible By 5,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1018. 可被 5 整除的二进制前缀
给定由若干
0
和1
组成的数组A
。我们定义N_i
:从A[0]
到A[i]
的第i
个子数组被解释为一个二进制数(从最高有效位到最低有效位)。返回布尔值列表
answer
,只有当N_i
可以被5
整除时,答案answer[i]
为true
,否则为false
。
示例 1:
输入:[0,1,1] 输出:[true,false,false] 解释: 输入数字为 0, 01, 011;也就是十进制中的 0, 1, 3 。只有第一个数可以被 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]
提示:
1 <= A.length <= 30000
A[i]
为0
或1
解法一
//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:vector<bool> prefixesDivBy5(vector<int>& A) {int n = A.size();vector<bool> vec(n);int num = 0;for(int i = 0; i < n; i++) {num = 2 * num + A[i];vec[i] = (num %= 5) == 0 ? true : false;}return vec;}
};
思路:
此题就是一个进制转换问题,将二进制转为十进制数,再对5取余,依次填入数组中并返回。很容易写出如下代码:
class Solution {
public:vector<bool> prefixesDivBy5(vector<int>& A) {int n = A.size();vector<bool> vec(n);int num = 0;for(int i = 0; i < n; i++) {num = 2 * num + A[i];vec[i] = num % 5 == 0 ? true : false;}return vec;}
};
这个思路大体是正确的,问题在于int位有限,而1<=A.length<=30000,当A的位数太多时就会出现乘法溢出。
代码中num表示了数组A中前i项二进制位所构成的十进制数。每次i向右前进一位,相当于num *= 2,再加上第i位A[i],也就是循环体内产生溢出错误的这一句: num = 2 * num + A[i]
。
考虑num可以是任意一个数,分解成如下形式:
num = 5 * a + b,其中0 <= b <= 4
其中的5 * a项,乘以2之后同样是5的倍数,并不影响是否能被5整除这个问题,所以我们可以在每次计算完num之后,令num %= 5,这样可以把num每一步都控制在5以内,肯定不会有溢出问题了。
改进后的代码就是解法一。
这篇关于1018. Binary Prefix Divisible By 5的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!