【leetcode】1963. 使字符串平衡的最小交换次数

题目描述

leetcode.cn/problems/…/description

思路

水题, 贪心即可.
首先, 对于单个的闭括号, 一定要和一个开括号配对, 否则无法平衡. 以"][]["这个样例为例, 他以闭括号开头, 也就是说, 无论如何这个括号序列都需要交换一次位置. 这时, 我们假设开括号的价值为11, 那么为了平衡, 闭括号的价值就是−1-1. 从前开始遍历这个序列, 用一个变量表示经历过的所有的括号的价值和, 一但这个和小于00意味着什么, 意味着这个位置有没有和他配对的开括号, 这时不行的, 必须要交换一次位置.
交换一次位置之后, 后面就会有一个闭括号失去作用, 也就是说, 不需要再计算这个括号的价值了, 给价值和再加上一平衡掉(算上补齐−1-1的那个值一共就是22了).

代码

impl Solution {
    pub fn min_swaps(s: String) -> i32 {
        let mut ans = 0;
        let mut res = 0;
        for i in s.chars() {
            if i == '[' {
                res += 1;
            } else {
                res -= 1;
            }
            if res < 0 {
                ans += 1;
                res += 2;
            }
        }
        ans
    }
}

摸摸