記述された操作を実行した後の、長さ 1 ～ N の各プレフィックス内の各小文字の数

この問題では、各文字列プレフィックスに対して指定された操作を実行する必要があります。最後に、各文字の頻度をカウントする必要があります。

貪欲アルゴリズムを使用して、この問題を解決できます。長さ K の各プレフィックスを取得し、指定された条件に従ってその文字を更新する必要があります。マップを使用して、最終的な文字列内の文字の頻度を計算できます。

問題文 - N 個の小文字のアルファベットを含む文字列 tr が与えられています。さらに、合計 26 個の要素を含むマッピング リストが与えられます。各要素は、その値に基づいて小文字にマップされます。たとえば、mapping[0] は「a」にマップされ、mapping[1] は「b」にマップされ、mapping[25] は「z」にマップされます。さらに、マップされた配列には 1 または -1 が含まれます。

次のことを行う必要があります。

• 長さ K のプレフィックスから最大文字数を取得し、「マッピング」配列からマッピング値を取得します。

• マップされた値が 1 の場合、すべてのプレフィックス要素を 1 ずつ増やします。

• マップされた値が -1 の場合、すべてのプレフィックス要素を 1 ずつ減分します。

ここで、要素の追加とは、「a」 -> 「b」、「b」 -> 「c」、… 「z」 -> 「a」を意味します。

要素の減少は、「a」->「z」、「b」->「a」、…を意味します。 「z」→「y」。

長さ 1

例例

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

イラスト

長さ 1 のプレフィックスでは、最大の文字は「p」で、-1 にマップされます。したがって、更新された文字列は「orogress」になります。

長さ 2 のプレフィックスでは、最大文字は「r」で、マッピングは -1 です。したがって、更新された文字列は「nqogress」になります。

• 長さ 3 のプレフィックスでは、最大の文字は「q」で、マッピング値は 1 です。したがって、更新された文字列は「orpgress」になります。

• すべての作業が完了すると、最終的な文字列は「pqmfpdqr」になります。これには、「f」が 1 つ、「p」が 2 つ、「q」が 2 つ、「m」が 1 つ、「d」が 1 つ含まれます「だ」「る」。出力では、結果の文字列内の各文字の頻度を出力します。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- すべての操作を実行すると、最終的な文字列は「ac」となり、各文字の頻度が出力されます。

• 方法 1

このメソッドでは、文字列を反復処理し、インデックス P に等しい K の値を取得します。その後、長さが P に等しいプレフィックスを取得し、最大の文字を見つけて、マップされた値を取得し、それに応じてすべてのプレフィックス文字を更新します。

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

ステップ 1 - 「max_char」変数を定義して、指定されたプレフィックスの最大文字数を保存します。

ステップ 2 - 同様に、最終的な文字列内の各文字の頻度を保存するために、長さ 26 のリストをゼロで初期化します。

ステップ 3- 文字列のループを開始し、ループ内で「max_char」変数を 96 で初期化します。

ステップ 4

- ネストされたループを使用して、長さ p の接頭辞から最大の文字を見つけます。

ステップ 5

- max_char のマップされた値を追加して、プレフィックスの各文字を更新します。

ステップ 7

- 更新された文字が「a」より小さい場合は、「z」に更新します。

ステップ 8

- 更新された文字が「z」より大きい場合は、「a」に更新します。

ステップ 9

- 最後に、更新された文字列をループして、各文字の頻度をリストに保存します。

ステップ 10

- 文字の頻度を出力します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- 文字列を走査するために 2 つのネストされたループを使用するため、O(N*N)。

空間複雑度

- O(1)。文字の頻度を保存するために定数空間を使用するためです。 ＃＃＃結論は＃＃＃ 入力文字列に対して指定された操作を実行し、更新された文字列の文字頻度を出力に出力します。プログラマは、リストを使用する代わりに C のマップを使用して文字の頻度を保存することもできます。さらに練習するために、プログラマは、更新された文字列内の各文字の累積頻度を出力してみることができます。

以上が記述された操作を実行した後の、長さ 1 ～ N の各プレフィックス内の各小文字の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。