Codility BinaryGap in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 3 Minutes
  • 2017年5月22日

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

利用python built-in函数bin()将十进制输入转换为二进制字符串,遇到字符‘0’,计数器count += 1,遇到字符‘1’,计数器清空。变量max记录count最大值,函数最后返回max。但是有一个问题,转换为二进制表示的N没有前导0,但需要注意处理后缀0,以免错误计数。否则,若二进制表示为1001000时,函数返回3而不是2。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(N):
# write your code in Python 2.7
if (N > 2147483647 or N < 1):
return 0
s = bin(N)[2:]
last = s.__len__()-1
while (s[last] == '0'):
last -= 1
s = s[0:last+1]
count = 0
max = 0
for c in s:
if (c == '0'):
count += 1
if (count > max):
max = count
else:
count = 0
return max