当前位置：首页 > article >正文

LeetCode 1963.使字符串平衡的最小交换次数：计数模拟(不需要麻烦的“三种写法一步步优化”)

article 2025/3/20 11:29:29

【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 <= 10⁶
n 为偶数
s[i] 为'[' 或 ']'
开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

解题方法：计数模拟

题目保证[和]的数量是相同的，也就是说一定可以通过交换达成配对。

使用两个变量： $z u o Q ianY o u$ (左前右)和 $z u o$ 分别记录“[前]”的数量和“未被消耗的[”的数量。

遍历字符串

如果当前字符是[，就说明后续可以有一个]来和它配对并将他“消费”， $z u o + = 1$
如果当前字符是]，就看有无[以供配对：
- 如果 $zuo\gt 0$ ，说明有未配对的[，消耗之（ $z u o - = 1$ ）
- 否则(没有未配对的[)， $z u o Q ianY o u + = 1$

存在“无法配对的[前]”就说明要发生交换。但是注意 $z u o Q ianY o u$ 个“[前]”只需要交换 $\lceil\frac{zuoQianYou}{2}\rceil$ 次，因为]和后面某个[交换后，实际上[的数量也加一了，顺便就还能与一个]配对。

时间复杂度 $O (l e n (s))$
空间复杂度 $O (1)$

对于某“三种写法，一步步优化”，看似看完恍然大悟，实则完全没必要那么麻烦。因为这“一步步优化”实则大概是其作者的思考过程罢了。若能直接想到简单方法，就直接想吧！尝试几次就能发现之前想法可能存在的漏洞了。但不可否认这位作者绝大多数文章还是十分优质的。

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:16:25
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:17:39
 */
class Solution {
public:
    int minSwaps(string s) {
        int zuoQianYou = 0, zuo = 0;
        for (char c : s) {
            if (c == '[') {
                zuo++;
            } else {
                if (zuo) {
                    zuo--;
                } else {
                    zuoQianYou++;
                }
            }
        }
        return (zuoQianYou + 1) / 2;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-17 12:18:42
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-17 12:18:42
'''
class Solution:
    def minSwaps(self, s: str) -> int:
        zuoQianYou = zuo = 0
        for c in s:
            if c == '[':
                zuo += 1
            else:
                if zuo:
                    zuo -= 1
                else:
                    zuoQianYou += 1
        return (zuoQianYou + 1) // 2

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:21:49
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:21:49
 */
class Solution {
    public int minSwaps(String s) {
        int zuoQianYou = 0, zuo = 0;
        for (char c : s.toCharArray()) {
            if (c == '[') {
                zuo++;
            } else {
                if (zuo > 0) {
                    zuo--;
                } else {
                    zuoQianYou++;
                }
            }
        }
        return (zuoQianYou + 1) / 2;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-17 12:20:26
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-17 12:21:31
 */
package main

func minSwaps(s string) int {
    zuoQianYou, zuo := 0, 0
    for i := range s {
        if s[i] == '[' {
            zuo++
        } else {
            if zuo > 0 {
                zuo--
            } else {
                zuoQianYou++
            }
        }
    }
    return (zuoQianYou + 1) / 2
}