建構具有重複限制的字串-php教程-PHP中文網

Construct String With Repeat Limit

2182。建構具有重複限制的字串

難度：中

主題：雜湊表、字串、貪婪、堆疊（優先權佇列）、計數

給定一個字串 s 和一個整數 RepeatLimit。使用 s 的字元建構一個新字串repeatLimitedString，使得字母不會連續出現超過重複限制次數連續。您不必必須使用 s 中的所有字元。

回傳字典中最大的可能的repeatLimitedString。

如果在a 和b 不同的第一個位置，字符串a 的字母在字母表中出現的字母晚於b 中對應的字母，則字符串a 按字典順序 大於字符串b。如果前 min(a.length, b.length) 個字元沒有不同，則較長的字串是字典順序上較大的字串。

範例1：

輸入： s = "cczazcc"，repeatLimit = 3
輸出：「zzcccac」
解釋：我們使用 s 中的所有字元來構造重複限製字串「zzcccac」。
- 字母「a」最多連續出現 1 次。
- 字母「c」最多連續出現 3 次。
- 字母「z」最多連續出現 2 次。
- 因此，連續出現的字母不會超過repeatLimit 次，並且該字串是有效的repeatLimitedString。
- 該字串是字典中可能的最大的重複限製字串，因此我們傳回「zzcccac」。
- 請注意，字串「zzcccca」按字典順序更大，但字母「c」連續出現超過 3 次，因此它不是有效的重複限製字串。

範例2：

輸入： s = “aababab”，repeatLimit = 2
輸出：「bbabaa」
解釋：我們只使用 s 中的部分字元來構造重複限製字串「bbabaa」。
- 字母「a」最多連續出現2次。
- 字母「b」最多連續出現 2 次。
- 因此，連續出現的字母不會超過repeatLimit 次，並且該字串是有效的repeatLimitedString。
- 該字串是字典中可能的最大的重複限製字串，因此我們傳回「bbabaa」。
- 請注意，字串「bbabaaa」按字典順序更大，但字母「a」連續出現超過 2 次，因此它不是有效的 RepeatLimitedString。

約束：

1 5
s 由小寫英文字母組成。

提示：

開始按字元降序建構字串。
當達到repeatLimit時，選擇下一個最大的字元。

解：

我們使用貪婪方法來優先考慮字典順序上較大的字符，同時確保沒有字符連續超過repeatLimit。此方法使用優先權佇列（最大堆）以字典順序降序處理字符，並確保沒有字符連續出現超過repeatLimit次數。

解決方案說明

統計字元：使用陣列統計字串s中每個字元出現的頻率。
最大堆：使用最大堆（優先隊列）按字典順序降序排序和提取字元。
貪婪構造：
- 新增最大可用字符，最多重複限制次數。
- 如果達到當前字符的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）連續追加到結果字串中。
- 如果某個字元達到其重複限制，請暫時停止追加它。
- 使用臨時佇列來保存仍有剩餘計數但暫時跳過的字元。
處理重複限制：
- 如果目前字元已達到重複限制，則使用佇列中按字典順序排列的下一個最大字元。
- 將前一個字元重新插入頻率圖中以便稍後繼續處理。
邊緣情況：
- 角色最初可能不會用完其全部計數。
- 處理完佇列中的備份字元後，目前字元將會恢復處理。

如何運作

字元計數：$freq 追蹤所有字元的出現次數。
最大堆：SplPriorityQueue 用作最大堆，其中字元依其 ASCII 值（降序）排列優先權。
字串建構：
- 如果目前字元已達到其重複限制，則取得下一個最大的字元。
- 使用下一個最大的字元一次，並將前一個字元恢復到堆中以供將來使用。
最終結果：結果字串是滿足repeatLimit約束的字典順序最大的字串。

範例演練

輸入：

s = "cczazcc", 重複限制 = 3

步驟：

頻率計數：

['a'=> 1、'c' => 4、'z' => 2]
降序排列：

['z'=>; 2、'c' => 4、'a' => 1]
在遵守重複限制的同時附加字元：
- 追加「z」→「zz」（z 計數 = 0）
- 追加「c」3次→「zzccc」（c計數= 1）
- 追加「a」→「zzccca」（計數 = 0）
- 追加剩餘的「c」→「zzcccac」

輸出：「zzcccac」

時間複雜度

字元頻率計數：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
?>

登入後複製