题解 | #求最大连续bit数#
求最大连续bit数
https://www.nowcoder.com/practice/4b1658fd8ffb4217bc3b7e85a38cfaf2
Python3
方法一
while True:
try:
n = bin(int(input())).strip('0b')
cnt = 0
res = []
for i in n:
if i == '1':
cnt += 1
if i == '0' and cnt != 0:
res.append(cnt)
cnt = 0
res.append(cnt)
print(max(res))
except:
break
时间复杂度O(N)，空间复杂度O(N)。
方法二：改进方法一
while True:
try:
n = bin(int(input())).strip('0b')
cnt = 0
max_cnt = 0
for i in n:
if i == '1':
cnt += 1
if i == '0' and cnt != 0:
max_cnt = max(cnt, max_cnt)
cnt = 0
max_cnt = max(cnt, max_cnt)
print(max_cnt)
except:
break
空间复杂度降低O(1)，时间复杂度还是O(N)不变。方法三：以0分割
while True:
try:
n = bin(int(input())).strip('0b')
l = [len(i) for i in n.split('0')]
print(max(l))
except:
break
时间复杂度O(log2n)，空间复杂度O(N)
方法四：位运算
while True:
try:
n = bin(int(input())).strip('0b')
l = len(n)
n = int(n, 2)
cnt = 0
for i in range(l):
if n != 0:
n &= n << 1
cnt += 1
print(cnt)
except:
break
