• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

5840. 使字符串平衡的最小交换次数 力扣(中等) 第255场oppo周赛 猜出来的

admin

11月 28, 2021

5840. 使字符串平衡的最小交换次数

给你一个字符串 s ,下标从 0 开始 ,且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 ‘[‘ 和 n / 2 个闭括号 ‘]’ 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 :

字符串是一个空字符串,或者
字符串可以记作 AB ,其中 A 和 B 都是 平衡字符串 ,或者
字符串可以写成 [C] ,其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

示例 1:

输入:s = “][][“
输出:1
解释:交换下标 0 和下标 3 对应的括号,可以使字符串变成平衡字符串。
最终字符串变成 “[[]]” 。

题解:

统计未匹配的左括号的数量 c,每次遇到左括号就加一,遇到右括号就减一。

如果遇到右括号并且 c=0,那么就需要到字符串末尾找一个左括号并交换。

代码:

class Solution {
public:
    int minSwaps(string s) {
    
    int k=0,res=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='[') k++;
            else k--;
        if(k<0) res=k<res?k:res;        
    }
     res=-res;
     res=res-res/2;
     return res;
    }
};

题解代码:https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/solution/go-tan-xin-by-endlesscheng-7h9n/class Solution {

public:
int minSwaps(string s) {
  int cnt = 0, mincnt = 0;
  for (char ch: s)
  {
       if (ch == '[')  cnt += 1;
       else 
          {
        cnt -= 1;
        mincnt = min(mincnt, cnt);
     }
  }
  return (-mincnt + 1) / 2;
  }
}; 
class Solution {
public:
int minSwaps(string s) {
  int l=0,res=0;
  for (char ch: s)
  {
       if (ch == '[')  l++;   // 遇到左括号直接+
       else                    // 遇到右括号
          {
             if (l>0) l--;    // 如果有多的左括号,可以直接和当前遇到右括号配对
               else           // 否则需要进行交换
               {
                     l++;
                     res++;
               }
        }
  }
  return   res;
  }
};    

发表回复

您的电子邮箱地址不会被公开。