位运算强化

佚名 6年前 (2019-04-14) 随笔 1866人围观抢沙发百度已收录

1018. 可被 5 整除的二进制前缀

思路：尽量不要通过int(str,2)转换成10进制，太慢。时间超越78%的python提交用户，内存超越64%的python提交用户

1 class Solution(object):
2     def prefixesDivBy5(self, A):
3         res=[]
4         val=0
5         for each in A:
6             val=val*2+each   # 左移增大2倍
7             res.append(True if val % 5 == 0 else False)
8         return res

思路二：慢时间比思路一慢4倍

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 class Solution(object):
 2     def prefixesDivBy5(self, A):
 3         res = []
 4         A = "".join([str(i) for i in A])
 5         for i in range(len(A)):
 6             if int(A[:i+1], 2) % 5 == 0:
 7                 res.append(True)
 8             else:
 9                 res.append(False)
10         return res
11                 
12             
13

1017. 负二进制转换

思路：先计算余数，然后减去余数后在除以-2 。时间超越100%的python用户提交，内存超越17.95%的python用户提交

 1 class Solution(object):
 2     def baseNeg2(self, N):
 3         if N==0:
 4             return "0"
 5         res=[]
 6         while N:
 7             res.append(abs(N%(-2)))
 8             N=(N-res[-1])//(-2)
 9         return "".join([str(x) for x in res[::-1]])
10

1016. 子串能表示从 1 到 N 数字的二进制串

思路：大佬说：[1024, 2047]这些数字均为11位二进制表示，并且彼此不同，而11位的子串只有S.length()-10<990个，所以N>2047不可能。
具体为什么我也不清楚。

 1 class Solution(object):
 2     def queryString(self, S, N):
 3         """
 4         :type S: str
 5         :type N: int
 6         :rtype: bool
 7         """
 8         if N>2047:  # 不然第25个测试用例无法通过
 9             return False
10         for  i in range(1,N+1):
11             if bin(i)[2:] not in S:
12                 return False
13         return True
14

1015. 可被 K 整除的最小整数

思路：设置一个变量j记录数字的长度。时间超越100%的Python提交。内存超越100%的用户提交

class Solution(object):
    def smallestRepunitDivByK(self, K):
        """
        :type K: int
        :rtype: int
        """
        
        if K%2==0 or K%5==0:
            return -1
        i,j=1,1
        while i%K!=0:
            i%=K
            i=i*10+1
            j+=1
        return j