2

インタビューの質問に遭遇しました：

入力 String: が与えられた場合、aaaaabcddddeeそれを に変換しa5b1c1d4e2ます。

追加の制約の 1 つは、これをインプレースで行う必要があることです。これは、余分なスペース (配列) を使用しないことを意味します。

エンコードされた文字列が常に元の文字列に収まることが保証されています。つまり、元の文字列よりも多くのスペースを占有abcdeするようにエンコードされるため、string likeは発生しません。a1b1c1d1e1

インタビュアーが私にくれたヒントの 1 つは、文字列を 1 回トラバースして、節約されたスペースを見つけることでした。

それでも、追加の変数を使用しないと、入力文字列の一部の値が上書きされる可能性があるため、私は立ち往生しています。

何か提案をいただければ幸いです。

4

4 に答える 4

9

これは良いインタビューの質問です.

キーポイント

重要なポイントは 2 つあります。

  1. c11 文字は;としてエンコードする必要があります。
  2. エンコードされた長さは常に元の配列よりも小さくなります。

1 以降、各文字をエンコードするには少なくとも 2 つの場所が必要であることがわかっています。つまり、単一の文字のみがより多くのスペースをエンコードする必要があります。

シンプルなアプローチ

重要なポイントから、単一の文字がエンコード中に多くの問題を引き起こすことがわかります。エンコードされた文字列を保持するのに十分な場所がない可能性があるからです。では、最初にそれらを残し、最初に他の文字を圧縮するのはどうですか?

たとえば、aaaaabcddddee最初に 1 文字を残して後ろからエンコードすると、次のようになります。

aaaaabcddddee
_____a5bcd4e2

次に、十分なスペースがあるようにキー ポイント 2 を指定すると、部分的にエンコードされたシーケンスを最初から安全にエンコードすることができます。

分析

解決策が見つかったようですが、これで終わりですか? いいえ、次の文字列を検討してください。

aaa3dd11ee4ff666

この問題は文字の範囲を制限しないので、数字も使用できます。この場合、同じアプローチを引き続き使用すると、次のようになります。

aaa3dd11ee4ff666
__a33d212e24f263

では、ランレングスと元の文字列の数値をどのように区別しますか?

さて、何か他のことを試す必要があります。

Encode Benefit (E)を次のように定義しましょう:エンコードされたシーケンスと元の連続した文字シーケンスの間の長さの差。.

たとえば、aahas はE = 0にaaエンコードされるためa2、長さの違いはありません。aaaとしてE = 1エンコードされa3、エンコードされたものとオリジナルの長さの差は です1。1 文字のケースを見てみましょうE。はい、-1です。E定義から、 :の式を推測できますE = ori_len - encoded_len。

では、問題に戻りましょう。キーポイント 2 から、エンコードされた文字列は常に元の文字列よりも短くなることがわかっています。Eこのキーポイントをどのように言い換えればよいでしょうか?

非常に単純です:はsigma(E_i) >= 0、i番目の連続する文字部分文字列の です。E_iEncode Benefit

たとえば、問題で指定したサンプル:aaaaabcddddeeは、次の 5 つの部分に分けることができます。

E(0) = 5 - 2 = 3  // aaaaa -> a5
E(1) = 1 - 2 = -1 // b -> b1
E(2) = 1 - 2 = -1 // c -> c1
E(3) = 4 - 2 = 2  // dddd -> d4
E(4) = 2 - 2 = 0  // ee -> e2

シグマは次のようになります3 + (-1) + (-1) + 2 + 0 = 3 > 0。これは、エンコード後に 3 つのスペースが残ることを意味します。

ただし、この例から、潜在的な問題が見られる可能性があります。合計を行っているため、最終的な答えが 0 より大きい場合でも、途中でマイナスになる可能性があります。

はい、これは問題であり、非常に深刻です。Eが下回った場合0、これは現在の文字をエンコードするのに十分なスペースがなく、その後の文字を上書きすることを意味します。

しかし、しかし、なぜ最初のグループから合計する必要があるのでしょうか? 負の部分をスキップするために途中から合計を開始できないのはなぜですか? 例を見てみましょう：

2 0 -1 -1 -1 1 3 -1

-1最初から合計すると、インデックス 4 (0 ベース) で3 番目を追加すると 0 を下回ります。インデックス 5 から合計し、最後に到達したときにインデックス 0 にループバックする場合、問題はありません。

アルゴリズム

分析により、アルゴリズムに関する洞察が得られます。

  1. 最初から開始しE、現在の連続するグループを計算し、合計に追加しE_totalます。
  2. E_totalがまだ負でない場合(>= 0)、問題はなく、安全に次のグループに進むことができます。
  3. E_totalが 0 を下回った場合、現在の位置からやり直す必要があります。つまり、クリアE_totalして次の位置に進みます。

シーケンスの最後に到達してE_totalもまだ負でない場合、最後の開始点は良い開始点です! このステップにはO(n)時間がかかります。通常はループバックして再度確認する必要がありますが、ポイント 2 以降、確実に有効な答えが得られるので、ここで安全に終了できます。

次に、開始点に戻って従来のランレングス エンコーディングを開始できます。最後に到達したら、シーケンスの最初に戻って最初の部分を終了する必要があります。注意が必要なのは、文字列の末尾にある残りのスペースを使用する必要があることです。その後、順序の問題が発生した場合に備えてシフトを行う必要があり、余分な空白を削除すると、最終的に完了です:)

したがって、解決策があります (コードは疑似であり、検証されていません)。

// find the position first
i = j = E_total = pos = 0;
while (i < s.length) {
    while (s[i] == s[j]) j ++;
    E_total += calculate_encode_benefit(i, j);
    if (E_total < 0) {
        E_total = 0;
        pos = j;
    }
    i = j;
}

// do run length encoding as usual:
// start from pos, end with len(s) - 1, the first available place is pos
int last_available_pos = runlength(s, pos, len(s)-1, pos);
// a tricky part here is to make use of the remaining spaces from the end!!!
int fin_pos = runlength(s, 0, pos-1, last_available_pos);
// eliminate the white
eliminate(s, fin_pos, pos);
// update last_available_pos because of elimination
last_available_pos -= pos - fin_pos < 0 ? 0 : pos - fin_pos;
// rotate back
rotate(s, last_available_pos);

複雑

アルゴリズムには 4 つの部分があります。

  1. 開始場所を見つける:O(n)
  2. 文字列全体に対する Run-Length-Encoding:O(n)
  3. 空白の除去:O(n)
  4. その場での文字列の回転:O(n)

したがってO(n)、合計で持っています。

視覚化

この文字列をエンコードする必要があるとします。abccdddefggggghhhhh

最初のステップとして、開始位置を見つける必要があります。

Group 1: a     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 1;
Group 2: b     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 2;
Group 3: cc    -> E_total += 0  -> E_total = 0 >= 0 -> proceed;
Group 4: ddd   -> E_total += 1  -> E_total = 1 >= 0 -> proceed;
Group 5: e     -> E_total += -1 -> E_total = 0 >= 0 -> proceed;
Group 6: f     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 9;
Group 7: ggggg -> E_total += 3  -> E_total = 3 >= 0 -> proceed;
Group 8: hhhhh -> E_total += 3  -> E_total = 6 >= 0 -> end;

したがって、開始位置は 9 になります。

         v this is the starting point
abccdddefggggghhhhh
abccdddefg5h5______
             ^ last_available_pos, we need to make use of these remaining spaces
abccdddefg5h5a1b1c2
d3e1f1___g5h5a1b1c2
      ^^^ remove the white space
d3e1f1g5h5a1b1c2
          ^ last_available_pos, rotate
a1b1c2d3e1f1g5h5

最後の言葉

この質問は些細なことではなく、実際にはいくつかの伝統的なコーディング面接の質問を自然に結び付けています. 推奨されるマインド フローは次のようになります。

  1. パターンを観察し、重要なポイントを見つけます。
  2. スペースが不足している理由は、1 文字のエンコードが原因であることに気付きます。
  3. 連続する文字グループごとにエンコードの利点/コストを量子化します (別名Encoding Benefit )。
  4. 元のステートメントを説明するために提案した量子化を使用します。
  5. 適切な出発点を見つけるためのアルゴリズムを見つけます。
  6. 適切な出発点でランレングス エンコーディングを行う方法を理解する。
  7. エンコードされた文字列を回転させ、空白を削除する必要があることを理解してください。
  8. その場で文字列の回転を行うアルゴリズムを見つけます。
  9. その場で空白を削除するアルゴリズムを見つけてください。

正直なところ、インタビュー対象者が短時間でしっかりとしたアルゴリズムを考え出すのは少し難しいので、分析フローは非常に重要です。何も言わずに、あなたのマインドフローを見せてください。これは、面接官があなたの現在の段階を知るのに役立ちます.

于 2016-04-10T11:02:48.893 に答える
0

通常どおりにエンコードするだけかもしれませんが、出力インデックスが入力インデックスを追い越すことがわかった場合は、「1」をスキップしてください。次に、終了したら、後ろに戻り、カウントのないすべての文字の後に 1 を挿入し、残りの文字列を元に戻します。最悪の場合（文字の繰り返しなし）はO（N ^ 2）なので、もっと良い解決策があると思います。

編集:最終的な文字列が常にソースに収まるという部分を見逃したようです。その制限により、ええ、これは最適なソリューションではありません。

EDIT2: それの O(N) バージョンは、最初のパス中に、最終的な圧縮された長さ (一般的にはソースよりも長くなる可能性があります) を計算し、ポインター p1 をそれに設定し、ポインター p2 を圧縮された文字列に設定します。 1 が省略された場合 (したがって、p2 は <= p1)、必要に応じて p2 を p1 にコピーし、1 を追加して、両方のポインターで逆方向に進みます (これが発生すると、p2 と p1 の差が減少します)。

于 2016-04-10T10:32:38.737 に答える