快速查找2的幂的数字
快速查找2的幂的数字
提问于 2013-09-22 17:54:34
任务是搜索2^10000以下的所有2的幂，返回字符串所在的第一次幂的索引。例如，如果要搜索的给定字符串是"7“，程序将输出15，因为2^15是其中包含7的第一个幂。
我是通过暴力尝试来解决这个问题的，大约70%的测试用例都会超时。
for i in range(1,9999):
if search in str(2**i):
print i
break如何在5秒的时间限制下实现这一点？
回答 6
Stack Overflow用户
发布于 2013-09-22 17:56:10
尽量不要在每一步都计算2^i。
pow = 1
for i in xrange(1,9999):
if search in str(pow):
print i
break
pow *= 2你可以边走边计算。这应该会节省大量的计算时间。
使用xrange将阻止构建列表，但这在这里可能不会有太大区别。
in可能是作为二次字符串搜索算法实现的。使用像KMP这样的东西进行字符串搜索可能(也可能不是，你必须测试一下)更有效。
Stack Overflow用户
发布于 2013-09-22 18:35:45
一种更快的方法是直接以十进制计算数字。
def double(x):
carry = 0
for i, v in enumerate(x):
d = v*2 + carry
if d > 99999999:
x[i] = d - 100000000
carry = 1
else:
x[i] = d
carry = 0
if carry:
x.append(carry)那么搜索函数就可以变成
def p2find(s):
x = [1]
for y in xrange(10000):
if s in str(x[-1])+"".join(("00000000"+str(y))[-8:]
for y in x[::-1][1:]):
return y
double(x)
return None还要注意，2^10000的所有幂的位数只有1500万，搜索静态数据的速度要快得多。如果不能每次都重新启动程序，那么
def p2find(s, digits = []):
if len(digits) == 0:
# This precomputation happens only ONCE
p = 1
for k in xrange(10000):
digits.append(str(p))
p *= 2
for i, v in enumerate(digits):
if s in v: return i
return None使用这种方法，第一次检查将需要一些时间，下一次将非常非常快。
Stack Overflow用户
发布于 2013-09-22 19:07:18
计算每个2的幂，并使用每个字符串构建一个后缀树。这是所有字符串大小的线性时间。现在，查找基本上是每个查找字符串长度的线性时间。
我不认为你可以在计算复杂性方面胜过它。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18942546
复制相关文章
相似问题
腾讯云开发者
