时间戳

首页 > 解决方案 > Python 代码运行时间过长

python - Python 代码运行时间过长

问题描述

我遇到的问题是以“ok”开头将所有“o”更改为“ko”，将“k”更改为“ok”1000次，然后计算有多少个连续的o。一旦代码达到两位数，代码就会显着变慢，我不确定如何重构我的代码。

import string
y ="ok"
z = ""
for c in range(1000):
    for x in y:
        if str(x) == "o":
            x = x.replace("o", "ko")
            z += x
        else:
            x = x.replace("k", "ok")
            z += x
        y = z
    z = ""
    print(y,c)
y = y.replace("k", " ")
y = y.count("oo")
print (y)

来源问题

基思向一位朋友大喊大叫后，收到一条由一个字母组成的消息：“K”。对这种不费吹灰之力的反应感到愤怒，他回答“OK”，他的朋友回答“KOOK”。一个精明的人，基思识别出他的朋友所煽动的模式：随后的消息包括基思和他的朋友将每个“K”替换为“OK”，将“O”替换为“KO”。帮助 Keith 找出 1000 回复的消息中有多少组长度为 2 或更大的连续 Os。第一条消息“K”不算作回复。给出你的答案 mod 10^9 + 7。

澄清什么构成“长度为 2 或更大的连续 Os 集”： KOKOOKOOOKOOOO - 此字符串中有三组长度为 2 或更大的连续 K（“OO”、“OOO”、“OOOO”）。

标签： pythonfor-loopreplacescripting

解决方案

这里的主要问题是字母的数量每一步都会翻倍——比如说，在第 40 步期间，有 2^40 个字母。如果每个字母占用一个字节，那就是大约 TB 的字母。当然，与存储所有 1000 步所需的空间相比，这只是很小的一部分。所以，不，像这样暴力破解问题是不可行的。

相反，目标可能会识别出该模式是Thue-Morse 序列，但有时会翻转。'o' 和 'k' 对应 0 或 1，这并不重要。您可以搜索维基百科页面以查找序列中连续“1”的最大数量。

推荐阅读