[leetcode] 1018. Binary Prefix Divisible By 5

[leetcode] 1018. Binary Prefix Divisible By 5

Description

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]Output: [true,false,false]Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: [1,1,1]Output: [false,false,false]

Example 3:

Input: [0,1,1,1,1,1]Output: [true,false,false,false,true,false]

Example 4:

Input: [1,1,1,0,1]Output: [false,false,false,false,false]

Note:

1 <= A.length <= 30000.A[i] is 0 or 1.

分析

题目的意思是：给定一个数组，判断一第i个数为结尾的二进制数能够被5整除，返回一个bool数组。这道题我想着暴力破解一下，发现A的长度能够达到30000，按照直觉这个地方会存在溢出，结果却没有溢出，python太厉害了啊，膜拜一下，如果不溢出那就能够暴力破解了哈。这道题出得有点失败啊， 更好的解法因该是：​​​ Solution: def prefixesDivBy5(self, A: List[int]) -> List[bool]: n=len(A) prev=0 res=[] for i in range(n): prev=prev<<1 cur=prev+A[i] if(cur%5==0): res.append(True) else: res.append(False) prev=cur return res

参考文献

​​[LeetCode] python easy to understand and 100% memory, runtime beats 70.53 %​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。