python - 解决“超出时间限制”的任何方法

Question

代码是计算一个范围内的数字，转换为二进制形式，其中没有连续的“11”

class Solution(object):
    def findIntegers(self, n):
        if 1 <= n <= pow(10,9):
            count=0
            for item in range(n+1):
                num=str("{0:b}".format(item))
                if "11" not in num:
                    count+=1
        else:
            raise ValueError
        return count

我相信它会返回正确的输出，但是对于输入“100000000”的 leet 代码问题，它会返回“超出时间限制”

用这个输入运行代码，是的，它非常慢。我想提高运行时质量，但除了使用循环和 .format() 之外想不出新方法

对于那些可能想要更多细节的人来说，这是我坚持的问题。

标签： pythonbinaryruntime

Answer 1

如评论中所述，该解决方案可在 leet 代码中获得并且解释得很好，但是这里有一个注释的 python 实现

def recursive_find_nums(binaryLen, sumSoFar, targetNum, lastDigit):
    if sumSoFar > targetNum:
        # we have exceeded the limit, this number does not count
        return 0
    if (1 << binaryLen) > targetNum:
        # the next depth will exceed our limit
        # but this number counts
        return 1
    zeros = recursive_find_nums(binaryLen+1,sumSoFar,targetNum,0)
    if lastDigit == 1:
        # since lastDigit is 1 we can only add 0 to our binary string
        return zeros
    else:
        # since lastDigit == 0 we can add 1 or 0 to our string
        ones = recursive_find_nums(binaryLen+1,sumSoFar + (1 << binaryLen),targetNum,1)
        return zeros + ones

考虑二进制1010（9，它没有 2 个连续的 1），因为它以零结尾，我们可以添加 1 或零，产生10101或10100

现在我们看看那些匹配的 2 个（只要它们不超过我们的目标值）正弦10100仍然以零结尾我们遵循上面相同的逻辑

但是，由于10101以 1 结尾，我们只能在末尾添加一个零，如果我们要添加一个 1，我们将违反我们的规则，因此101010我们可以通过在末尾添加一个 1 或零来获得唯一的匹配值

因为我们从零开始，我们可以添加一个 1 或一个零

1或者0

1遵循上面的 1 规则（我们只能将其扩展为 '0'），ergo 1 => 10 as the only path that follows our rule (10` 是十进制的 2）

因为0我们遵循与上面相同的 `0 -> 1 或 0（因此 2 个分支符合我们的规则）

当我们递归增加 binaryLength 和 sum 时，我们覆盖了所有允许的分支（与每个值相反，但我们确实探索了一些被修剪的坏分支）

顺便说一下，这里是你的方法和这个方法（在对数刻度上）和没有 对数刻度之间的速度差异

当...

它仍然太慢了......哈哈，哦，好吧，用另一种方法