13

SPOJ の STRSEQから:

数字の文字列を指定して、指定された文字列にサブシーケンスとして出現しない最小の非負の整数を見つけます。

0 から段階的に数を見つけるアプローチを試みましたが、私のアプローチはO(answer * length of the string). O(length of string)この問題に対するアプローチはありますか?

例:

入力

  • 9876543210
  • 21698921085321984125
  • 12345678901

出力

  • 11
  • 7
  • 22
4

1 に答える 1

8

このアルゴリズムに必要なデータ構造:

  • ビットセットの配列、入力文字列要素ごとに 1 つのビットセット (および最後にもう 1 つの空のビットセット)、桁ごとに 1 ビット (各ビットセットのサイズは 10)
  • 10 スタックの位置 - 各桁 (オプション)
  • カウンター (答えの桁数を数える)

アルゴリズム：

  1. 入力文字列を逆方向にスキャンし、現在の位置をこの位置の数字に対応するスタックにプッシュし、前の位置からビットセットをコピーして、現在の位置の数字に対応するビットを設定します。現在のビットセットのすべてのビットが設定されたら、カウンターをインクリメントし、ビットセットをクリアします。
  2. カウンターがまだゼロの場合、現在のビットセットの最下位ビットを取得し、このビットに対応する 1 桁を使用して結果の数値を作成します。
  3. 唯一の未設定ビットが「ゼロ」の場合、結果の数値は「10」として構成され、その後にステップ 4 の結果が続きます (最初の数字「0」は事前に決定されています)。
  4. 現在のビットセットの最下位ゼロ ビットを取得し (ただし、このステップが初めて実行されるときは、「0」に対応するビットを無視します)、それを結果の次の桁として使用し、この桁に対応するスタックをポップします (取得するまで)現在の位置以上の位置)、現在の位置をこのスタックからのインデックスに 1 を加えた値に設定します。現在の位置に対応するビットセットを取得し、ステップ 4 を繰り返します。このステップは、「カウンター + 1」回、または空のスタックをポップする試行まで実行する必要があります。

代替アルゴリズム:

他の代替手段は、ほとんどの計算をステップ 4 からステップ 1 に移動することです。この場合、ビットセット配列と 10 個のスタックの代わりに、さらに単純なデータ構造が必要です。

説明と例:

このアルゴリズムのステップ 1 は、サブシーケンスとして任意の 1 桁の数字を含む最短のサフィックスを決定します。次に、このサフィックスに隣接し、1 桁の数字も含む最短の部分文字列を見つけます。これらを組み合わせると、任意の 2 桁の数字を含む最短の接尾辞が得られます。このプロセスは、3 桁、4 桁のサフィックスなどについても続けられます。また、この前処理ステップでは、これらの n 桁の数字の左側にどの数字を書き込むことができるかを判断し、対応するサブシーケンスが入力文字列のサフィックスに存在するようにします。 (この情報はビットセットに含まれています)。

たとえば、入力文字列の場合、12345678901このステップでは、インデックス「1」で始まる接尾辞に 1 桁の数字が含まれている可能性があると判断されます。また、次の方法でビットセットを埋めます。

index: bitset:
10     0000000010
9      0000000011
8      1000000011
7      1100000011
6      1110000011
5      1111000011
4      1111100011
3      1111110011
2      1111111011
1      0000000000
0      0000000010

ステップ 2 と 3 では、いくつかのまれなケースを扱います。

ステップ 4 は、位置 "0" のビットセットを調べて、最小の開始桁を見つけることから始まります。この例では、ビット "1" が設定されています。これは、2 桁の数字を "1" で始めることができないことを意味します (そのような数字はすべて文字列に含まれています)。また、「0」から始めることはできません。次の unset ビットは「2」なので、番号を「2」から始めます。

対応するスタックを使用するか、文字列を順番に検索して、最初の数字「2」の位置に到達することができます。数字の残りの桁は、数字「2」の後に始まる接尾辞にある必要があります。このサフィックスの開始位置のビットセットは「1111111011」です。これは、このサフィックスで唯一の未使用の数字が「2」であることを意味します。「counter+1」は 2 で、ステップ 4 の反復を 2 回使用したので、ここで終了します。したがって、答えは「22」です。

これは、時間の複雑さが劣る他のアルゴリズムO(answer + length of the string)です。

数字 (0 から 9) ごとに、インデックスの配列を準備します。各インデックスは、指定された位置または右側にある最も近い数字の出現を指します。例えば：

For string     216989210...
and digit "1": 11777777...

これは、入力配列を逆方向にスキャンすることで実装できます。適切な数字が表示されるとすぐに、そのインデックスをインデックス配列に書き込み始めます。上記の例では、これは、位置 7 で右端の数字 "1" を確認し、インデックス 1 で数字 "1" の別の発生が確認されるまで、インデックス配列を 7 で埋めることを意味します。次に、残りの位置をこのインデックスで埋めます。

O(answer * length of the string)これで、OP に記載されているアルゴリズムの複雑さを からに簡単に減らすことができますO(answer + length of the string)。現在の数値の次の桁の最も近い位置を取得するには、インデックス配列の 1 つによって提供されるリンクをたどるだけです。

たとえば、最初の 61 個の非負の数を試してから、数 "61" について、最初の位置で "6" のインデックス配列を調べて、インデックス "2" を見つけることができます (このインデックスは既に見つかっているため、これは実際には必要ありません)。 "60" を処理している間)、次の位置 (2+1) で "1" のインデックス配列を調べて、インデックス "7" を見つけます。つまり、指定された文字列に「61」があり、「62」を続けることができます...

于 2013-10-29T14:24:51.710 に答える