LeetCode.1018-可被5整除的二进制数(Binary Prefix Divisible By 5)


这是小川的第379次更新,第407篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第241题(顺位题号是1018)。给定0和1的数组A,考虑N_i:从A[0]A[i]的第i个子数组被解释为二进制数(从最高有效位到最低有效位)。

返回布尔值answer列表,当且仅当N_i可被5整除时,answer[i]true

例如:

输入:[0,1,1]
输出:[true,false,false]
说明:二进制输入数字为0,01,011,转为十进制数,分别为0,1和3。只有第一个数字可以被5整除,所以answer[0]true

输入:[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

02 解题

题目的意思是A中都是二进制位的0和1,依次从左到右,判断二进制组成的十进制数能否被5整除,将每次的判断结果存入List

按照常规的操作,循环A中的元素,组成一个二进制字符串,再转成十进制数,再对5取余,将判断结果存入List中,但是有个问题需要考虑,A的长度上限是30000,如果组合成的二进制字符串长度过长,是否还能被转成整数?答案存疑,那我们需要换另外一种思路来解决问题了。

结合例子来看,[1,1,1,0,1],从左往右看:
第一次计算,二进制数为1,转为十进制为1,1%5=1。
第二次计算,二进制数为11,转为十进制为3,(1*2+1)%5 = 3%5 =3。
第三次计算,二进制数为111,转为十进制为7,(3*2+1)%5 = 7%5 =2。
第四次计算,二进制数为1110,转为十进制为14,(2*2+0)%5 = 4%5 = 14%5 =4。
第五次计算,二进制数为11101,转为十进制为29,(4*2+1)%5= 9%5 = 29%5 =4。

从例子中可以看到,新的二进制数是在前一次二进制数的基础上左移一位得到的,即 num[i+1] = (A[i]<<1) + A[i+1]A[i]为前一次的十进制整数,A[i+1]为在前一次二进制数尾部新加的0或1,题目只是需要我们判断每次新组成的二进制数能否被5整除,我们可以利用前一次取余的结果左移,因为其中能被整除的部分是不太需要关心的,这样可以避免数字过大超出范围的风险。

public List<Boolean> prefixesDivBy5(int[] A) {
    List<Boolean> answer = new ArrayList<Boolean>();
    int num = 0;
    for (int i=0; i<A.length; i++) {
        // 写成 num = (num<<1) + A[i]; 也是一样的效果
        num = num*2 + A[i];
        num %= 5;
        answer.add(num == 0);
    }
    return answer;
}


小结

算法专题目前已连续日更超过七个月,算法题文章247+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!


作者:程序员小川,发布于:2019/07/11
原文:https://www.cnblogs.com/xiaochuan94/p/11167822.html