0

誰かが私に質問した

Find the longest alphabetically increasing or equal string 
composed of those letters. Note that you are allowed to drop 
unused characters.

So ghaaawxyzijbbbklccc returns aaabbbccc.

Is an O(n) solution possible?

そして、私はそれをコード[Pythonで]実装しました

s = 'ghaaawxyzijbbbklccc'
lst = [[] for i in range(26)]

for ch in s:
    ml = 0
    for i in range(0,ord(ch) + 1 - ord('a')):
        if len(lst[i]) > len(lst[ml]):
            ml= i
    cpy = ''.join(lst[ml])
    lst[ord(ch) - ord('a')] = cpy + ch

ml = 0
for i in range(26):
    if len(lst[i]) > len(lst[ml]):
        ml = i
print lst[ml]

答えは「aaabbbccc」です

私はこれをいくつかの例で試してみましたが、すべてうまくいきました! このコードの複雑さが O(N) であると考えることができる限り、例を挙げてみましょう。文字列 'zzzz' があると仮定すると、メイン ループは 4 回実行され、内部ループは反復ごとに 26 回実行されるので、次のことができます。最悪の場合、コードが実行されると言う

O(26*N + 26)
---------^-
this is the last iteration

O（N）は受け入れられますか？

今質問は

  1. ideone のO(N)私のコードで動作しますか?
  2. O(N) で動作する場合、DP の O(N2)コードの DPを使用する理由
  3. このコードよりも良いですかフレンズコード
  4. このコードの制限
4

2 に答える 2

-1

これは、最長増加サブシーケンスのバリエーションです。違いは、要素が「a」から「z」までしか実行できないため、要素が制限されていることです。あなたのアルゴリズムは確かにO(N)です。O(N log N) は、たとえば上記のリンクのアルゴリズムを使用して可能です。可能な要素の数の制限により、これは O(N) になります。

于 2015-06-16T08:16:27.320 に答える