1963.使字符串平衡的最小交换次数:计数模拟(不需要麻烦的“三种写法一步步优化”)
【LetMeFly】1963.使字符串平衡的最小交换次数:计数模拟(不需要麻烦的“三种写法一步步优化”)
力扣题目链接:https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-string-balanced/
给你一个字符串 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
解题方法:计数模拟
题目保证[
和]
的数量是相同的,也就是说一定可以通过交换达成配对。
使用两个变量:$zuoQianYou$(左前右)和$zuo$分别记录“[
前]
”的数量和“未被消耗的[
”的数量。
遍历字符串
如果当前字符是
[
,就说明后续可以有一个]
来和它配对并将他“消费”,$zuo+=1$如果当前字符是
]
,就看有无[
以供配对:- 如果$zuo\gt 0$,说明有未配对的
[
,消耗之($zuo-=1$) - 否则(没有未配对的
[
),$zuoQianYou+=1$
- 如果$zuo\gt 0$,说明有未配对的
存在“无法配对的[
前]
”就说明要发生交换。但是注意$zuoQianYou$个“[
前]
”只需要交换$\lceil\frac{zuoQianYou}{2}\rceil$次,因为]
和后面某个[
交换后,实际上[
的数量也加一了,顺便就还能与一个]
配对。
- 时间复杂度$O(len(s))$
- 空间复杂度$O(1)$
对于某“三种写法,一步步优化”,看似看完恍然大悟,实则完全没必要那么麻烦。因为这“一步步优化”实则大概是其作者的思考过程罢了。若能直接想到简单方法,就直接想吧!尝试几次就能发现之前想法可能存在的漏洞了。但不可否认这位作者绝大多数文章还是十分优质的。
AC代码
C++
1 |
|
Python
1 |
|
Java
1 |
|
Go
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
1963.使字符串平衡的最小交换次数:计数模拟(不需要麻烦的“三种写法一步步优化”)
https://blog.letmefly.xyz/2025/03/17/LeetCode 1963.使字符串平衡的最小交换次数/