文字列を反転するために必要な隣接スワップの最小数

文字列 str を指定すると、隣接する文字を交換するだけで文字列を反転できます。隣接する文字を交換するだけで、文字列を逆にするために必要な最小移動数を見つける必要があります。必要な解決策を見つけるために 2 つのメソッドを実装し、コードの説明と実装を提供します。

例例

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

まず、最後の文字を最初の位置に移動します。これには 4 回の交換が必要です。その後、文字列は「jshke」になります。次に、「e」を 2 番目の位置に移動します。これには 3 回の交換が必要になります。同様に、「k」の場合は 2 つのスワップが必要ですが、「h」の場合は 1 つのスワップのみが必要で、最終的な答えは 10 になります。

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

まず、2 番目のインデックスの文字を交換し、最後のインデックスに移動します。これには 2 回の交換が必要で、文字列は「abcea」になります。次に、「b」を「e」に交換します。交換には 2 回かかり、文字列は「aceba」になります。次に、さらに 2 回の交換を実行して、最終的な反転文字列を取得します。これには、合計 6 回の交換が必要です。

素朴なアプローチ

の中国語訳は次のとおりです:

素朴なアプローチ

上記の例を見てきました。次に、正しいコードを実装するために必要な手順を見てみましょう。

• まず、指定された文字列をパラメータとして受け取り、必要な最小ステップ数を戻り値として返す関数を作成します。

• この関数では、文字列のコピーを作成し、それを反転して元の文字列と比較します。

• 3 つの変数を作成します。最初の 2 つは文字列を反復処理するために使用され、最後の 1 つは必要なステップ数を保存するために使用されます。

• while ループを使用して、指定された文字列を反復処理し、現在のインデックス値が反転した文字列と同じになる反復回数だけスキップし続けます。

• 次に、while ループを使用して、「j」が「i」に達するまで隣接する文字を交換し、交換するたびにカウントをインクリメントします。

• 最後に、カウントの値を返し、main 関数で出力します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(N^2) です。ここで、N は指定された文字列の長さです。ネストされた while ループを使用して、反復中に N の因数を与えます。 上記のコードの空間計算量は O(N) です。これは、指定された文字列の反転を格納するために追加の文字列を作成するためです。

注

- ここでは別のアプローチも可能ですが、非常に高度なデータ構造を使用する必要があります。このメソッドのコンセプトは、最後の文字から開始して、最初の文字が条件を満たすまでチェックできるということです。その後、理論的には、その文字を最後の位置に移動し、その位置を完了としてマークし、その値を高レベルのデータ構造に保存できます。

次に、各キャラクターについて、まだタグ付けされていない後ろから出現する同じキャラクターを見つけ、その後の要素の合計数からタグ付けされた要素の数を引いた値までカウントを増やします。 ＃＃＃結論は＃＃＃ このチュートリアルでは、隣接する文字のみを交換して特定の文字列を反転するために必要な最小ステップ数を見つけるコードを実装しました。ネストされた while ループを使用し、指定された文字列のコピーを反転して解決策を見つけました。上記のコードの時間計算量は O(N^2) です。ここで、N は文字列のサイズであり、空間計算量は O(N) です。

以上が文字列を反転するために必要な隣接スワップの最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。