4

任务是搜索 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 秒的时间限制下如何解决这个问题？

4

6 回答 6

5

尽量不要2^i在每一步都计算。

pow = 1
for i in xrange(1,9999):
    if search in str(pow):
        print i
        break
    pow *= 2

您可以随时计算它。这应该会节省大量的计算时间。

Usingxrange将阻止构建列表，但这可能不会有太大的不同。

in可能实现为二次字符串搜索算法。使用KMP之类的东西进行字符串搜索可能会（也可能不会，你必须测试）更有效。

于 2013-09-22T09:56:10.313 回答
4

一种更快的方法可能是直接以十进制计算数字

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 的 2 的所有幂的位数仅为 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

使用这种方法，第一次检查需要一些时间，接下来的检查会非常非常快。

于 2013-09-22T10:35:45.113 回答
2

只有10000个数字。您不需要任何复杂的算法。只需提前计算它们并进行搜索。这应该只需要 1 或 2 秒。

powers_of_2 = [str(1<<i) for i in range(10000)]

def search(s):
    for i in range(len(powers_of_2)):
        if s in powers_of_2[i]:
            return i
于 2013-09-22T11:10:39.840 回答
2

计算每个 2 的幂并使用每个字符串构建一个后缀树。这是所有字符串大小的线性时间。现在，查找基本上是每个查找字符串长度的线性时间。

我认为您无法在计算复杂性方面击败它。

于 2013-09-22T11:07:18.140 回答
0

尝试这个

twos = []
twoslen = []
two = 1
for i in xrange(10000):
    twos.append(two)
    twoslen.append(len(str(two)))
    two *= 2

tens = []
ten = 1
for i in xrange(len(str(two))):
    tens.append(ten)
    ten *= 10

s = raw_input()
l = len(s)
n = int(s)

for i in xrange(len(twos)):
    for j in xrange(twoslen[i]):
        k = twos[i] / tens[j]
        if k < n: continue
        if (k - n) % tens[l] == 0:
            print i
            exit()

这个想法是预先计算 2、10 的每个幂，并且还预先计算 2 的每个幂的位数。这样，​​问题就简化为找到存在 j 的最小值 i，这样在删除最后一个 j 之后来自 2 ** i 的数字，您获得一个以 n 结尾的数字或表示为公式 (2 ** i / 10 ** j - n) % 10 ** len(str(n)) == 0。

于 2013-09-22T10:38:48.817 回答
0

这里的一个大问题是，将二进制整数转换为十进制表示法所花费的时间是位数的二次方（至少以 Python 的直接方式）。正如@6502 在他的回答中所做的那样，伪造自己的十进制算术实际上更快。

但是让 Python的模块来做这件事要快得多decimal——至少在 Python 3.3.2 下（我不知道decimal在那之前的 Python 版本中内置了多少 C 加速）。这是代码：

class S:
    def __init__(self):
        import decimal
        decimal.getcontext().prec = 4000  # way more than enough for 2**10000
        p2 = decimal.Decimal(1)
        full = []
        for i in range(10000):
            s = "%s<%s>" % (p2, i)
            ##assert s == "%s<%s>" % (str(2**i), i)
            full.append(s)
            p2 *= 2
        self.full = "".join(full)

    def find(self, s):
        import re
        pat = s + "[^<>]*<(\d+)>"
        m = re.search(pat, self.full)
        if m:
            return int(m.group(1))
        else:
            print(s, "not found!")

和示例用法：

>>> s = S()
>>> s.find("1")
0
>>> s.find("2")
1
>>> s.find("3")
5
>>> s.find("65")
16
>>> s.find("7")
15
>>> s.find("00000")
1491
>>> s.find("666")
157
>>> s.find("666666")
2269
>>> s.find("66666666")
66666666 not found!

s.full是一个超过 1500 万个字符的字符串。它看起来像这样：

>>> print(s.full[:20], "...", s.full[-20:])
1<0>2<1>4<2>8<3>16<4 ... 52396298354688<9999>

所以字符串包含 2 的每个幂，指数跟随在尖括号中的幂。该find()方法构造一个正则表达式来搜索所需的子字符串，然后向前查找以查找幂。

玩弄这个，我相信几乎任何搜索方式都“足够快”。它正在获取占用大量时间的大国的十进制表示。该decimal模块解决了那个问题。

于 2013-09-23T00:19:27.777 回答