文字列のバランスを整えるための最小スワップ数

1963 年。使琴弦平衡最少的交換次數

難度：中

主題： 兩個指標、字串、堆疊、貪婪

給你一個0索引的字串s，偶數長度為n。字串由剛好 n / 2 個左括號'['和n / 2 個右括號']'組成。

字串稱為平衡當且僅當：

• 是空字串，或
• 可以寫成AB，其中A和B都是平衡字串，或
• 可以寫成[C]，其中C是一個平衡字串。

您可以在任意兩個索引處任意次數交換括號。

回傳最小交換次數以使s平衡。

範例1：

• 輸入： s = "][]["
• 輸出： 1
• 說明：您可以透過交換索引 0 和索引 3 來平衡字串。
  • 結果字串是「[[]]」。

範例2：

• 輸入： s = "]]][[["
• 輸出： 2
• 說明：您可以執行以下操作來平衡字串：
  • 將索引 0 與索引 4 交換。 s = "[]][][".
  • 將索引 1 與索引 5 交換。 s = "[[][]]".
  • 結果字串是「[[][]]」。

範例 3：

• 輸入： s = "[]"
• 輸出： 0
• 解釋： 字串已經平衡。

約束：

• n == s.length
• 2 6
• n 是偶數。
• s[i] 是“[”或“]”。
• 左括號 '[' 的數量等於 n / 2，右括號 ']' 的數量等於 n / 2。

提示：

1. 迭代字串並追蹤每一步中左括號和右括號的數量。
2. 如果右括號的數量越來越多，則需要進行交換。
3. 與最靠近 s 末尾的左括號交換。

解：

我們可以使用雙指標方法，在考慮到限制的情況下，這種方法是有效的。

方法：

1. 追蹤平衡：當我們迭代字串時，我們可以追蹤左括號和右括號之間的平衡：

   • 遇到「[」時增加餘額。
   • 遇到']'時減少餘額。

2. 辨識不平衡：當餘額變成負數時，表示字串中該點的右括號「]」多於左括號「[」。這是我們需要交換括號以使字串平衡的地方。

3. 計算交換：修正不平衡：

   • 保留一個計數器 max_imbalance 來追蹤迭代過程中觀察到的最大不平衡。
   • 所需的交換次數等於 (max_imbalance 1) / 2，這有效地給出了使字串平衡所需的最小交換次數。

讓我們用 PHP 實作這個解：1963。使琴弦平衡最少的交換次數

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

// Example usage:
$s1 = "][][";
echo minSwaps($s1); // Output: 1

$s2 = "]]][[[";
echo minSwaps($s2); // Output: 2

$s3 = "[]";
echo minSwaps($s3); // Output: 0
?>

解釋：

1. 餘額追蹤：

   • Balance 追蹤「[」和「]」數量之間的差異。
   • 如果餘額變成負數，則表示此時 ']' 數量多於 '['。

2. 計算最大不平衡:

   • max_imbalance 儲存迭代過程中遇到的最大不平衡。
   • 如果餘額變成負數，則將 max_imbalance 更新為 max_imbalance 或 -balance 中的較大者。

3. 計算掉期:

   • 要解決不平衡問題，所需的最小交換量為 (max_imbalance 1) / 2。

時間複雜度：

• 時間複雜度為O(n)，其中n是字串的長度。我們迭代字串一次以確定 max_imbalance。
• 空間複雜度為O(1)，因為我們使用一些變數來追蹤平衡和最大不平衡。

此解決方案確保我們滿足約束條件，即使對於大量輸入也是如此。

聯絡連結

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が文字列のバランスを整えるための最小スワップ数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。