0

これは、「コーディング インタビューをクラックする」Q1.3 からの質問です。「アルゴリズムを設計し、追加のバッファーを使用せずに文字列内の重複する文字を削除するコードを記述します。注: 1 つまたは 2 つの変数を追加しても問題ありません。配列ではありません。」うまく動作するように見えるプログラムを書きましたが、自分のプログラムと混同しています。ここにコードが添付されています。

string remove_duplicates(string &s1)
{
   int n=s1.size();
   for(int i=n-1; i!=-1; --i)
        for(int j=0; j<i; ++j)
        {
            if(s1[i]==s1[j])
            {
                int k=i;
                while(k!=n)
                {
                    s1[k]=s1[k+1];
                    k++;
                }
            }
        }
    return s1;
}

s1=abcdeafg の場合、このコードを使用すると、出力は abcdefg になります (入力が abababab の場合、出力は ab になります)。 2 番目の 'a' を s1 の末尾に移動します。説明してくれませんか？

4

1 に答える 1

2

s1 の長さは実際に変化しています。重複文字が見つかり、while(k!=n) ループを使用して重複文字を s1 の最後に移動している場合、ループの最後の繰り返しで k == n-1 の場合、コードは s1[ を評価しています。 n-1] = s1[n] であり、実際には s1[n-1] = '\0' であるため、s1 の長さは 1 だけ短くなります。

于 2012-07-21T22:14:25.263 に答える