2712.使所有字符相等的最小成本：脑筋急转弯(遍历)

【LetMeFly】2712.使所有字符相等的最小成本：脑筋急转弯(遍历)

力扣题目链接：https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal/

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

 

示例 1：

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

 

提示：

• 1 <= s.length == n <= 105
• s[i] 为 '0' 或 '1'

解题方法：遍历

如果$s[i - 1]\neq s[i]$，那么要么翻转$s[0,\dots,i - 1]$，要么翻转$s[i, \dots, n-1]$，才能使$s[i - 1]$和$s[i]$相等。所需要的最小成本是$\min(i, n - i)$。

并且翻转只会改变$s[i - 1]$和$s[i]$是否相同，不会影响其他相邻字符是否相同（相同的字符一起翻转后还是相同，不同的翻转后还是不同）。

累加所有相邻不相同位置的最小翻转成本即为答案。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-27 11:26:12
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-27 21:52:03
 */
typedef long long ll;
/*
010101
110101
000101
000100
000111
000000
*/
class Solution {
public:
    ll minimumCost(string s) {
        ll ans = 0;
        int n = s.size();
        for (int i = 1; i < n; i++) {
            if (s[i] != s[i - 1]) {
                ans += min(i, n - i);
            }
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-27 22:02:00
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-27 22:05:06
'''
class Solution:
    def minimumCost(self, s: str) -> int:
        ans = 0
        for i in range(1, len(s)):
            if s[i] != s[i - 1]:
                ans += min(i, len(s) - i)
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-27 22:08:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-27 22:11:31
 */
class Solution {
    public long minimumCost(String s) {
        long ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                ans += Math.min(i, s.length() - i);
            }
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-27 22:14:17
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-27 22:53:45
 * @Description: AC,100.00%,100.00%
 */
package main

func minimumCost(s string) (ans int64) {
    for i := 1; i < len(s); i++ {
        if s[i] != s[i - 1] {
            ans += int64(min(i, len(s) - i))
        }
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源