同じ文字位置を持つ文字数のパリティと周波数パリティ

この問題では、頻度と位置が同じパリティを持つ文字の数を数え、その数を奇数または偶数として出力します。

この問題を解決するには、文字列内の各文字の頻度を調べ、頻度と位置が同じパリティを持つ文字の総数を数えます。その後、カウントに基づいて奇数または偶数の答えを出力できます。

問題文- 英語のアルファベットの小文字のみを含む文字列 alpha が与えられています。同じ文字の位置と頻度を持つ文字の数が奇数か偶数かを確認する必要があります。

任意の文字が次の条件のいずれかを満たしている場合、その文字は同じ周波数と文字位置パリティを持ちます。

• 文字列内の文字の頻度が奇数で、文字の位置も奇数の場合。

• 文字列内の文字の頻度が偶数で、文字の位置も偶数の場合。

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

図解

a は周波数 1、位置 1 なのでパリティは同じでカウントは 1 になります。

d の周波数は 2、位置は 4 です。したがって、パリティビットは同じであるため、カウントは 2 になります。

カウント値は 2 であり、偶数です。＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明
• – 「p」のパリティのみが同じです。したがって、カウントは 1 となり、答えは奇数になります。

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

説明
• - パリティはどの文字でも同じではありません。したがって、カウント値はゼロなので、「偶数」と出力されます。
  方法1

このアプローチでは、マップ データ構造を使用して、各文字列文字の頻度を保存します。その後、文字の位置と頻度が同じパリティを持つ文字の数を数えます。

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

ステップ 1- 長さ 27 の count[] 配列を定義し、0 で初期化します。また、「パリティ」を0で初期化します。

ステップ 2- 文字の頻度を count[] 配列に保存します。

ステップ 3- 26 回繰り返して、各小文字のアルファベットを調べます。

ステップ 4- count[p] が 0 より大きい場合、文字の頻度と位置が同じパリティであるかどうかを確認します。その場合は、パリティ値を 1 増やします。

ステップ 5- 最後に、パリティが 2 で割り切れる場合は、「偶数」を返します。それ以外の場合は、「奇数」を返します。＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - 文字の頻度を計算するための O(N)。

空間複雑度 - O(26) ~ O(1) のアルファベット文字の頻度を格納します。

方法 2

このメソッドでは、指定された文字列を並べ替えます。その後、異なる隣接文字を取得するたびに、前の文字の頻度と位置パリティをチェックします。

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

ステップ 1

- 「パリティ」を 0 に初期化します。

ステップ 2

- sort() メソッドを使用して、指定された文字列を並べ替えます。

ステップ 3

- 文字列のトラバースを開始し、「charCnt」を 0 に初期化して、現在の文字の頻度を保存します。

ステップ 4

- 現在の文字が次の文字と異なる場合は、「charCnt」のパリティと文字位置が一致しているかどうかを確認します。その場合は、パリティを 1 増やします。

ステップ 5

- 現在の文字が前の文字と同じ場合は、「charCnt」を 1 増やします。

ステップ 6

- 最後に、「パリティ」値が偶数の場合は、「偶数」を返します。それ以外の場合は、「奇数」を返します。

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

時間計算量 - 文字列のソートに O(NlogN)。

スペースの複雑さ - 文字列のソートに O(N)。

最初の方法では定数スペースを使用しますが、2 番目の方法では動的スペースを使用して指定された文字列を並べ替えます。さらに、2 番目の方法は時間コストがかかるため、パフォーマンスを向上させるために最初の方法を使用することをお勧めします。

以上が同じ文字位置を持つ文字数のパリティと周波数パリティの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。