部分文字列のすべての文字をインクリメントして文字列回文を作成するために必要な最小移動数

コンピュータ サイエンスとプログラミングの分野では、問題を解決するための効率的なアルゴリズムを発見することが非常に重要です。興味深い問題は、部分文字列内のすべての文字を追加して文字列を回文に変換するために必要な操作の最小数を特定することです。この記事では、C プログラミング言語を使用してこの問題に対処する 2 つの方法を検討します。

これらのメソッドを詳しく説明する前に、使用する関数の構文を定義しましょう −

私たちの目標は、文字列を回文に変換する際の移動数を最小限に抑えることです。この問題は、次の主要な段階を経てアルゴリズムによって解決されます。 -

• まず、文字列の両側から 2 つのポインタ変数を作成します。左ポインタは文字列の先頭から開始し、右ポインタは文字列の末尾から開始します。

• 構成制限が許す限り、つまりいずれかのポインタがもう一方の停止を超えたらプロセスを続行します。 -

• 文字値が同じ場合は、2 つのポインタを近づけ続けます。文字値が異なる場合は常に、それ以降の操作を実行する前に、右側の文字値が (その違いに応じて) インクリメントされます。この増加は 'a' と 'c' の差に比例するため、str[right] が 'c' に等しく、str[left] が 'a' に等しい場合、str[right] を 2 増やします ('a '- 'c'=2)。それに応じて移動数を更新します。

• 左辺が右辺より大きくなると、文字列は回文になります。

• 方法 1: ブルート フォース クラッキング

このメソッドでは、考えられるすべての部分文字列を考慮し、各部分文字列に必要な最小移動数を計算します。最後に、計算されたすべての動きの最小値を返します。

説明

説明

入力文字列 str を必要最小限の移動数で回文に変換する minMovesToMakePalindrome という関数が作成されました。いくつかのステップバイステップの手順を使用して、それがどのように機能するかを説明します:

移動変数を 0 に初期化します。これは、必要な移動の総数を追跡する役割を果たします。 - 長さ変数は入力文字列 str の長さを記録するため、次のステップでは、対称位置が重ならないように for ループを使用して文字列の半分を反復します。 - 最後に、このループ内で、abs(str[i] - str[length - i - 1]) は 2 つの終了文字間の絶対差を計算します。

計算された差は、これらの位置のキャラクターを等しくするために必要な移動数を表します。この差を移動数に加算します。

必要なすべてのポジションを反復処理した後、必要な合計最小移動数を move 変数に保存します。この値を返します。

main 関数では、文字列 str を値「abcde」で初期化します。次に、minMovesToMakePalindrome 関数を呼び出し、str をパラメーターとして渡します。返される移動の最小数は、minMoves 変数に格納されます。最後に、結果をコンソールに出力します。

方法 2: 最適なダブル ポインター方法

このメソッドは 2 つのポインターを使用して、文字列の両端から同時にトラバースします。効率を考慮して、文字列を回文に変換する手法を採用しました。この手法では、入力の両端から文字を徐々に追加して一致させます。このアプローチにより、不必要な操作が最小限に抑えられ、精度や機能を損なうことなく、より高速な変換が可能になります。

説明

説明

次のコード例の目的は、最適な 2 ポインター アプローチを利用して、指定された文字列を回文に変換するために必要な最小移動数を決定することです。

これを実現するために、minMovesToMakePalindrome という関数を作成しました。この関数は文字列引数を受け取り、必要な合計移動数を返します。まず、移動回数のカウントに使用する変数を 0 に設定し、左右のポインタを初期化します。左ポインタは入力文字列の先頭 (インデックス 0) から開始し、右ポインタは入力文字列の末尾 (インデックス str.) から開始します。長さ() - 1)。

while ループは、文字列内のすべての要素をカバーするために、left が right 以上になるまで反復されます。各反復では、abs(str[right] - str[left]) を使用して、左と右の位置にある文字間の違いを見つけます。これは、これら 2 つの文字を同じにするために必要な移動回数を表します。この差の値を実行カウンターに追加して、合計の手数を取得します。

入力文字列の中心に向かって移動するにつれて、左ポインタをインクリメントし、右ポインタをデクリメントします。左右のポインター間の重なりがなくなったら、文字列を回文に変換します。

この時点で、'moves' に保存されている合計移動数を返します。main() では、前と同じ手順に従い、新しい入力文字列 'abcde' を宣言し、この引数を指定して minMovesToMakePalindrome を呼び出し、合計最小移動数を返します。この値をコンソールに出力する前に、新しい変数 'minMoves' に割り当てられる値。

以下のテキストでは、文字操作によって特定の文字列を部分文字列の回文に変換するために必要な手数を計算する問題に対する洞察と潜在的な答えを提供することを目的として、2 つの代替案が示されています。 1 つの方法はブルート フォース メソッドと呼ばれ、考えられるすべての部分文字列を包含します。一方、もう 1 つの方法は最適な 2 ポインタ メソッドと呼ばれ、必要な移動数を大幅に削減します。プログラマーは、これらのメカニズムを簡単に適用して、同様の障害を解決し、ソリューションを改善できます。

以上が部分文字列のすべての文字をインクリメントして文字列回文を作成するために必要な最小移動数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。