Q クエリの場合、次を中国語に翻訳します。 3 項文字列で、すべての回文部分文字列を削除するために置換する必要がある文字の最小数

回文文字列は、反転した文字列と等しい文字列です。 「0」、「1」、「2」を含む文字列と長さ N の配列 Q が与えられた場合、指定された配列の各インデックスは範囲を表し、その範囲は次の形式の値のペアで表されます。範囲内に回文部分文字列が存在しないことを確認するために、特定の範囲内で置換する必要がある文字の最小数を見つける必要があります。

例例

リーリー リーリー

説明

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

説明

0 から 4 の範囲には、2 つの回文 010 と 1001 があります。回文が残らないようにインデックス 2 を '2' に変更できます。

2 ～ 5 の範囲には、回文番号 010 が 1 つだけあり、最初の 0 を 2 に変更することで変更できます。

5 ～ 10 の範囲の数値には、回文番号 020、000、および 20002 があります。最初の 2 を「1」に、次のインデックスの「0」を「2」に、最後から 2 番目のインデックスの値を「1」に変更して、すべての回文を取り除くことができます。

素朴なアプローチ

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

素朴なアプローチ

このメソッドの目的は、指定された範囲のすべての組み合わせを取得し、回文を使用せずに組み合わせに必要な最小変更数を見つけることです。しかし、問題は時間の複雑さです。

このメソッドを実装するには、再帰呼び出しを行って文字列を走査する必要があります。各インデックスには 3 つの選択肢があるため、すべての文字列を取得する時間の計算量は 3^N になります。ここで、Q 個のクエリに答える必要があり、それぞれのケースについて、回文文字列を削除すると時間計算量が O(Q*N*(3^N)) になるかどうかを確認する必要があります。

再帰呼び出しの場合、N の空間を維持する必要があります。これは、空間の複雑さが O(N) であることを意味します。

ダイナミックプランニング

アイデア

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

アイデア

この質問の考え方は、指定された範囲で回文番号を見つける必要がないということです。回文番号の最小可能長は、偶数の場合は 2、奇数の場合は 3 です。

3 つの異なる文字があり、回文なしで指定された文字列を作成するにはそれらすべてが必要です。合計サイズまたはシーケンスの選択があり、回文が存在せず、これらのシーケンスが文字列 '012' の順列になるようにシーケンスを形成できます。

dp 配列またはベクトルを使用してすべての可能なケースを保存します。各シーケンスでは文字数が少なくなり、そのシーケンスを使用します。

＃＃＃実装＃＃＃

実装部分では、まず、文字列、シーケンス、DP ベクトル、シーケンスの数をパラメータとして受け取り、DP ベクトルを更新する関数を作成します。

この関数では、まず最初のインデックスの値を更新し、次に一致しないケースごとに DP ベクトルの現在のインデックスの値を更新します。

考えられるすべてのシーケンスを手動で入力して配列に保存し、DP ベクトルを作成する別の関数を作成します。

前処理の値を渡して上記の関数を呼び出し、それを 1 つずつ反復処理することで各クエリに応答します。

Example

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

Example

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

時間と空間の複雑さ

上記のコードの時間計算量は O(N Q) です。ここで、N は文字列内の文字数、Q はクエリの数です。 状態をサイズ N のベクトルに格納するため、上記のコードの空間計算量は O(N) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、回文文字列が残らないように、特定の範囲でクエリを実行するときに変更する必要がある最小文字数を見つけるコードを実装しました。このコードは、時間計算量 O(N Q) と空間計算量 O(N) の動的プログラミングの概念を使用して実装しました。

以上がQ クエリの場合、次を中国語に翻訳します。 3 項文字列で、すべての回文部分文字列を削除するために置換する必要がある文字の最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。