bugfix> python > 投稿

私が与えられた問題は、すべての "o"を "ko"で、 "k"を "ok"で1000回変更してから、 "ok"で始まる連続したoの数を数えることです。コードは2桁に達すると大幅に遅くなり、コードをリファクタリングするために何をすべきかわかりません。

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)

ソースの問題

After ranting at length to a friend, Keith receives a message consisting of a single letter: "K". Incensed at this low-effort response, he responds with "OK", to which his friend replies "KOOK." An astute individual, Keith identifies the pattern instigated by his friend: subsequent messages consist of Keith and his friend replacing each "K" with "OK" and "O" with "KO". Help Keith find how many sets of consecutive Os of length two or greater are in the message on the 1000 reply. The first message, "K", does not count as a reply. Give your answer mod 10^9 + 7.

To clarify what constitutes "sets of consecutive Os of length two or greater": KOKOOKOOOKOOOO - there are three sets of consecutive Ks of length two or greater in this string ("OO", "OOO", "OOOO").

回答 2 件
  • ここでの主な問題は、文字の数が各ステップで2倍になることです。したがって、たとえば、40番目のステップでは2 ^ 40文字になります。各文字が1バイトの場合、それは約テラバイトの文字です。もちろん、1000ステップすべてを保存するのにどれだけのスペースが必要かと比較すると、ほんのわずかです。このように、このような問題を総当たりすることは現実的ではありません。

    代わりに、目標はパターンがThue-Morseシーケンスであることを認識する可能性がありますが、場合によっては反転します。 「o」と「k」は0または1に対応し、特に問題ではありません。代わりに、ウィキペディアのページを検索して、シーケンス内の連続した「1」の最大数を見つけることができます。

  • y ="ok"
    for c in range(1000):
        y = y.replace('o','ko')
        y = y.replace('k','ok')
        print(y,c)
    
    

    「o」と「k」の置換をループで検索する必要はないかもしれませんが、それでも時間がかかります。

あなたの答え