繰り返し制限のある文字列を構築する-PHPチュートリアル-php.cn

繰り返し制限のある文字列を構築する

Susan Sarandon

リリース： 2024-12-24 08:44:19

オリジナル

731 人が閲覧しました

Construct String With Repeat Limit

2182。繰り返し制限のある文字列を構築

難易度: 中

トピック: ハッシュテーブル、文字列、Greedy、ヒープ (優先キュー)、カウント

文字列 s と整数のrepeatLimitが与えられます。行にrepeatLimit回を超える文字が出現しないように、sの文字を使用して新しい文字列repeatLimitedStringを構築します。 s のすべての文字を使用する必要はありません。

可能な 辞書編集上最大のrepeatLimitedStringを返します。

文字列 a は、a と b が異なる最初の位置に、b の対応する文字よりアルファベットの後ろに現れる文字がある場合、文字列 b よりも

辞書編集的に大きい。最初の min(a.length, b.length) 文字が異なっていない場合、長い文字列のほうが辞書編集的に大きい文字列となります。

例 1:

入力: s = "cczazcc"、repeatLimit = 3
出力: "zzcccac"
説明: s のすべての文字を使用して、repeatLimitedString "zzcccac" を構築します。

例 2:

入力: s = "aababab"、repeatLimit = 2
出力: "bbabaa"
説明: s の一部の文字のみを使用して、repeatLimitedString "bbabaa" を構築します。

制約:

ヒント:

文字の降順で文字列の構築を開始します。
repeatLimit に達したら、次に大きい文字を選択します。

解決策:

私たちは 貪欲なアプローチを使用して、辞書順に大きい文字を優先し、連続してrepeatLimitを超える文字がないようにします。このアプローチでは、優先キュー (最大ヒープ) を使用して文字を辞書編集上の降順で処理し、文字が連続してrepeatLimit 回を超えて出現しないようにします。

解決策の説明

文字数をカウント: 配列を使用して、文字列 s 内の各文字の頻度をカウントします。
最大ヒープ: 最大ヒープ (優先キュー) を使用して、文字を辞書編集上の降順に並べ替えて抽出します。
貪欲な建設:
- repeatLimit 回までに利用可能な最大の文字を追加します。
- 現在の文字のrepeatLimitに達した場合は、次に大きい文字に切り替えて一度挿入し、その後使用するために最初の文字をヒープに再挿入します。
エッジ処理: キャラクターがそれ以上使用できなくなった場合に適切に管理します。

このソリューションを PHP で実装してみましょう: 2182。繰り返し制限のある文字列を作成します

<?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

ログイン後にコピー

説明：

頻度カウント:
- 文字列 s を反復処理して、各文字の出現数をカウントします。
- 周波数を連想配列 $freq に保存します。
降順で並べ替えます:
- krsort() を使用して、文字を辞書編集順に降順順に並べ替えます。
結果の構築:
- 辞書編集上最大の文字 ($char) を結果の文字列に継続的に追加します。
- 文字がrepeatLimitに達した場合、一時的に追加を停止します。
- 一時キューを使用して、まだカウントが残っているが一時的にスキップされた文字を保持します。
ハンドルの繰り返し制限:
- 現在の文字がrepeatLimitに達している場合は、キューから辞書順に次に大きい文字を使用します。
- 前の文字を周波数マップに再挿入して、後で処理を続行します。
エッジケース:
- キャラクターは最初はフルカウントを使い果たさない場合があります。
- キューからバックアップキャラクターを処理した後、現在のキャラクターが処理を再開します。

仕組み

文字数: $freq はすべての文字の出現を追跡します。
最大ヒープ: SplPriorityQueue は最大ヒープとして使用され、文字は ASCII 値 (降順) によって優先されます。
文字列の構築:
- 現在の文字がrepeatLimitに達した場合は、次に大きい文字をフェッチします。
- 次に大きい文字を一度使用し、将来使用できるように前の文字をヒープに戻します。
最終結果: 結果の文字列は、repeatLimit 制約を満たす辞書編集上最大の文字列です。

チュートリアルの例

入力:

s = "cczazcc"、repeatLimit = 3

手順:

頻度カウント:

['a' => 1、'c' => 4、'z' => 2]
降順に並べ替えます:

['z' => 2、'c' => 4、'a' => 1]
repeatLimit を尊重しながら文字を追加します:
- 「z」→「zz」を追加 (z カウント = 0)
- 'c'を3回追加 → "zzccc" (c count = 1)
- 'a' → "zzccca" (a count = 0) を追加
- 残りの 'c' → "zzcccac" を追加

出力: "zzccccac"

時間計算量

文字頻度カウント: O(n)、n は文字列の長さです。
ヒープ操作: O(26 log 26)。ヒープは最大 26 文字を保持できます。
全体的な複雑さ: O(n 26 log 26) ≈ O(n).

空間の複雑さ

O(26) は周波数配列です。
O(26) ヒープ用。

テストケース

<?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

ログイン後にコピー