Codility BinaryGap in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 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