文章目錄

• • 題目
  • 題解

題目

題目來源：https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/

題解

分析：貪心。
對于括號序列，排除掉能夠匹配的[]之后，剩余的串有什么特點(diǎn)呢？其實(shí)，剩余的串是]]]....[[[這種格式，即左邊全是左括號，右邊全是右括號。

根據(jù)數(shù)學(xué)歸納法，]]]....[[[這種情況交換的次數(shù)是：左括號的數(shù)量 ÷ 2 向上取整。
比如]]][[[，左括號的數(shù)量為3，需要交換的次數(shù)為(3 + 1) / 2 = 2；
再比如][，左括號的數(shù)量為1，需要交換的次數(shù)為(1 + 1) / 2 = 1 ；
當(dāng)然，這里左括號的數(shù)量 = 右括號的數(shù)量。

下面的代碼中：變量l從左向右統(tǒng)計(jì)左括號的數(shù)量，與此同時(shí)，變量r統(tǒng)計(jì)右括號的數(shù)量，如果配對的話，讓l--；如果不配對的話，讓r++；
最終r中存的是剩余右括號的數(shù)量，亦等于剩余左括號的數(shù)量。
答案就是 (r + 1) / 2;

時(shí)間復(fù)雜度 O(n):遍歷一遍字符串
空間復(fù)雜度：常數(shù)級
ac代碼

class Solution { public:int minSwaps(string s) {int l = 0, r = 0;for ( const char c : s) {if (c == '[') {l++;}else {if (l > 0) l--;else r++;}}return (r + 1) / 2;} };

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Leetcode1963. 使字符串平衡的最小交换次数[C++题解]：贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。