バイナリ文字列内の等しくない文字とインデックスの文字ペアを交換することによって、文字列が回文文字列を形成できるかどうかをチェックします

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃問題文＃＃＃

文字列 str とバイナリ文字列 B があります。両方の文字列の長さは N に等しくなります。文字列 B 内に等しくない文字を含むインデックスのペアでその文字を複数回交換することで、文字列 str を回文文字列にできるかどうかを確認する必要があります。

例例

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

説明

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

説明

B[1] と B[2] は等しくないため、str[1] と str[2] を交換できます。最後の文字列は「ASA」にすることができます。

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

説明

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

説明

文字列 B には等しくない文字が含まれていないため、文字列を回文にすることはできません。

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

説明

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

説明

文字頻度が一致しないため、文字列 str を回文にすることはできません。

方法 1

最初のメソッドでは、文字列 str のすべての文字を使用して回文文字列を作成できるかどうかを確認します。そうである場合、文字列 B 内の異なる文字を含むインデックス ペアの文字を交換して、文字列を回文にできるかどうかを確認できます。それ以外の場合は false を返します。

＃＃＃アルゴリズム＃＃＃

ステップ 1

-utility() 関数を実行し、指定された条件に従って文字を交換し、文字の交換によって文字列が回文になるかどうかを判断します。

ステップ 2

- canBePalindromic() 関数を定義して、str の文字を使用して回文文字列を構築できるかどうかを確認します。

ステップ 2.1

-文字列 str の各文字とその頻度を保存するマップを作成します。 for ループを使用して文字列を反復処理し、文字の頻度をカウントします。

• ステップ 2.2

  - 偶数と奇数の頻度を持つ文字の数を数えます。

• ステップ 2.3

  - set を使用して、文字列内の一意の文字の合計数を取得します。

• ステップ 2.4

  -文字列の長さが奇数で、奇数の頻度で文字が 1 つだけ含まれている場合は true を返します。

• ステップ2.5

  -文字列の長さが偶数の場合、偶数の頻度を持つすべての文字と、奇数の頻度を持つ0文字はtrueを返します。

• ステップ2.6

  -falseを返します。

• ステップ 3

  - 文字列が回文にならない場合は、false を返します。

• ステップ 4

  - 文字列 B に複数の「1」と「0」が含まれる場合は true を返し、それ以外の場合は false を返します。

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

• 時間計算量 - O(NlogN)。for ループを使用して文字列を走査し、set の insert() メソッドに (logN) 時間がかかるためです。

• 空間複雑度 - O(K)、K は一意の文字の総数です。

• 方法 2 このメソッドでは、マップを使用する代わりに、配列を使用して文字の頻度を保存します。

  ＃＃＃アルゴリズム＃＃＃

ステップ 1

- 長さ 26 の 'charFrequancy' 配列を作成し、ゼロに初期化します。

• ステップ 2 - 文字列 B 内の 1 と 0 の合計数を数えます。

• ステップ 3 - 配列内の各文字の頻度を更新します。

ステップ 4

- 文字列の長さが偶数で、奇数の頻度がゼロでない場合は、false を返します。

• ステップ 5

  - 文字列の長さが奇数で、奇数の頻度が 1 より大きい場合は、false を返します。

• ステップ 6

  - 文字列に 1 と 0 の両方が存在する場合は true を返します。

• ステップ 7

  - false を返します。

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

• 時間計算量 - for ループを使用して文字列を反復処理するため、O(N)。

• 空間複雑度 - 常に長さ 26 の配列を使用するため、O(1)。

• ＃＃＃結論は＃＃＃

  与えられた条件に基づいて文字を交換することで、文字列が回文になるかどうかを確認する 2 つの方法を学習しました。最初の方法ではコレクションとマップを使用しますが、2 番目の方法では配列のみを使用してデータを保存します。 2 番目の方法は、コレクションにデータを挿入するのに insert() メソッドでは O(logn) 時間がかかるのに対し、配列では O(1) 時間しかかからないため、最初の方法よりも優れています。

以上がバイナリ文字列内の等しくない文字とインデックスの文字ペアを交換することによって、文字列が回文文字列を形成できるかどうかをチェックしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。