脚本宝典收集整理的这篇文章主要介绍了1963. 使字符串平衡的最小交换次数，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 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 <= n <= 106 n 为偶数 s[i] 为'[' 或 ']' 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2
实际代码中，可以不用编写「交换」的逻辑，这是因为我们总是选择最右边的左括号，因此在后续的遍历中，若遇到了这些左括号，在交换后的字符串上，该位置及后面必然全部是右括号，即此时该字符串已经是平衡的了。
因此，当遇到右括号并且此时 c=0c=0，可以直接将 cc 和答案加一，即视作将一个左括号和该右括号交换。由于没有实际交换括号，若后面又重新遇到了需要被交换的左括号，由于此时字符串已经是平衡的了，故不会对答案产生影响。
遍历字符串，遇到左括号cnt加一，遇到右括号减一，已知左括号和右括号数量相同，则只要在遍历过程中cnt不会小于0即可————这就要求左括号尽可能地早出现，而右括号尽可能地晚出现。不过要注意的是，']'和'['交换不意味着这个']'和这个'['配对。例如“]]][[[”，第一个右括号和最后一个左括号交换不意味着它们俩配对，交换之后得到“[]][[]”，可以看到它们分别和其它的一个右括号和左括号配对。
只遍历一次，遇到需要交换的地方才交换。
public int minSwaps(String s) {
//ans为交换次数
int ans=0,cnt=0;
for(int i=0;i<s.length();++i){
if(s.charAt(i)=='[') cnt++;
//当前字符为']'但前面没有多余的'['与之匹配，此时需要一次交换
else if(cnt==0){
ans++;
//交换之后该位置变成了'['，cnt需要加一
cnt++;
}
else cnt--;
}
return ans;
}
这种方法的关键在于需要看出来，未配对的情形一定是这种类型的：]]][[[，即未配对的右括号全部在未配对的左括号的左侧。为什么呢？因为未配对的右括号前面肯定不能出现未配对的左括号*，否则它们就配对了。
public int minSwaps(String s) {
/**
cnt1用于抵消可以匹配的左右括号
cnt2记录没匹配的对数，当前面没有多余的左括号且当前位置是右括号时有一对无法匹配，cnt2++；
*/
int cnt1=0,cnt2=0;
for(int i=0;i<s.length();++i){
if(s.charAt(i)=='[') cnt1++;
//cnt1不需要减一
else if(cnt1==0) cnt2++;
else cnt1--;
}
//若未匹配的对数是偶数，每一次交换可以实现两对成功配对
//若未匹配的对数是奇数，最后一次交换的左右括号相互配对，只有一对成功配对
return (cnt2+1)/2;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.COM/PRoblems/minimum-number-of-swaps-to-make-the-string-balanced 参考：https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/solution/go-tan-xin-by-endlesscheng-7h9n/
以上是脚本宝典为你收集整理的1963. 使字符串平衡的最小交换次数全部内容，希望文章能够帮你解决1963. 使字符串平衡的最小交换次数所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。