2712. 使所有字符相等的最小成本

题目描述

leetcode.cn/problems/…/description

思路

简单描述一下题目要求, 要把所有的字符全变成$1$或者全变成$0$, 可以从两种操作里选一种

• 从前面开始, 翻转到这个位置的所有字符, 每翻转一个字符加一点成本
• 从后面开始, 翻转到这个位置的所有字符, 每翻转一个字符加一点成本

很明显靠近前面的从前面开始翻转, 靠近后面的从后面开始翻转, 如果不一样就必须翻转, 把他们变成一样的.

WHY?

猜的, 感觉就是这样.

代码

impl Solution {
    pub fn minimum_cost(s: String) -> i64 {
        let mut s: Vec<char> = s.clone().chars().collect();
        let n = s.len();
        let mut ans = 0;

        if n == 1 {
            return 0;
        }

        // 只枚举一半
        for i in 0..n.div_ceil(2) {
            if s[i] != s[i + 1] { // 翻转前面
                ans += (i + 1) as i64;
                s[i] = s[i + 1];
            }
            if s[n - i - 2] != s[n - i - 1] { // 翻转后面
                ans += (i + 1) as i64;
                s[n - i - 1] = s[n - i - 2];
            }
        }

        ans
    }
}

看到官方题解的写法, 一个处理链就写完了
大受震撼

impl Solution {
    pub fn minimum_cost(s: String) -> i64 {
        s.chars()
            .collect::<Vec<_>>()
            .windows(2) // 滑动窗口
            .enumerate() // 获取下标
            .filter(|&(_, w)| w[0] != w[1]) // 只选不同的
            .map(|(i, _)| (i + 1).min(s.len() - (i + 1)) as i64) // 取最小值
            .sum() // 求和
    }
}