Medium

题目描述

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

  1. 选择一个下标 i 并反转从下标 0 到下标 i（两者都包含）的所有字符，成本为 i + 1
  2. 选择一个下标 i 并反转从下标 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 <= 10^5
  • s[i] 为 '0' 或 '1'

解题思路

解题思路

这道题的关键在于理解：最终的字符串中必定有至少一个位置的字符保持不变，其他位置都通过操作变成和这个位置相同的字符。

我们可以枚举每个位置作为"不变位置"，计算将整个字符串变成该位置字符所需的最小成本：

  1. 前缀成本计算：对于位置 i，计算将前缀 [0, i-1] 变成与 s[i] 相同的成本

    • 从左到右扫描，每当遇到与目标字符不同的字符时，需要执行第一种操作（从位置 0 反转到当前位置）
    • 由于可能需要多次操作才能让所有前缀字符变成目标字符，我们需要累计成本

  2. 后缀成本计算：对于位置 i，计算将后缀 [i+1, n-1] 变成与 s[i] 相同的成本

    • 从右到左扫描，每当遇到与目标字符不同的字符时，需要执行第二种操作（从当前位置反转到末尾）

  3. 贪心策略：对于前缀和后缀的处理，我们采用贪心方法：

    • 前缀处理：从左到右，一旦发现字符与目标不同就立即反转
    • 后缀处理：从右到左，一旦发现字符与目标不同就立即反转

最终答案是所有位置中 prefix[i] + suffix[i] 的最小值。

代码实现

class Solution {
public:
    long long minimumCost(string s) {
        int n = s.length();
        vector<long long> prefix(n, 0), suffix(n, 0);
        
        // 计算每个位置的前缀成本
        for (int i = 0; i < n; i++) {
            char target = s[i];
            long long cost = 0;
            for (int j = 0; j < i; j++) {
                if (s[j] != target) {
                    cost += j + 1;
                    // 反转 [0, j]
                    for (int k = 0; k <= j; k++) {
                        s[k] = (s[k] == '0') ? '1' : '0';
                    }
                }
            }
            prefix[i] = cost;
            // 恢复字符串
            for (int j = 0; j < i; j++) {
                if (s[j] != target) {
                    for (int k = 0; k <= j; k++) {
                        s[k] = (s[k] == '0') ? '1' : '0';
                    }
                }
            }
        }
        
        // 计算每个位置的后缀成本
        for (int i = 0; i < n; i++) {
            char target = s[i];
            long long cost = 0;
            for (int j = n - 1; j > i; j--) {
                if (s[j] != target) {
                    cost += n - j;
                    // 反转 [j, n-1]
                    for (int k = j; k < n; k++) {
                        s[k] = (s[k] == '0') ? '1' : '0';
                    }
                }
            }
            suffix[i] = cost;
            // 恢复字符串
            for (int j = n - 1; j > i; j--) {
                if (s[j] != target) {
                    for (int k = j; k < n; k++) {
                        s[k] = (s[k] == '0') ? '1' : '0';
                    }
                }
            }
        }
        
        long long result = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            result = min(result, prefix[i] + suffix[i]);
        }
        
        return result;
    }
};

class Solution:
    def minimumCost(self, s: str) -> int:
        n = len(s)
        s = list(s)  # 转换为可变列表
        prefix = [0] * n
        suffix = [0] * n
        
        # 计算每个位置的前缀成本
        for i in range(n):
            target = s[i]
            cost = 0
            for j in range(i):
                if s[j] != target:
                    cost += j + 1
                    # 反转 [0, j]
                    for k in range(j + 1):
                        s[k] = '1' if s[k] == '0' else '0'
            prefix[i] = cost
            # 恢复字符串
            for j in range(i):
                if s[j] != target:
                    for k in range(j + 1):
                        s[k] = '1' if s[k] == '0' else '0'
        
        # 计算每个位置的后缀成本
        for i in range(n):
            target = s[i]
            cost = 0
            for j in range(n - 1, i, -1):
                if s[j] != target:
                    cost += n - j
                    # 反转 [j, n-1]
                    for k in range(j, n):
                        s[k] = '1' if s[k] == '0' else '0'
            suffix[i] = cost
            # 恢复字符串
            for j in range(n - 1, i, -1):
                if s[j] != target:
                    for k in range(j, n):
                        s[k] = '1' if s[k] == '0' else '0'
        
        return min(prefix[i] + suffix[i] for i in range(n))

public class Solution {
    public long MinimumCost(string s) {
        int n = s.Length;
        char[] chars = s.ToCharArray();
        long[] prefix = new long[n];
        long[] suffix = new long[n];
        
        // 计算每个位置的前缀成本
        for (int i = 0; i < n; i++) {
            char target = chars[i];
            long cost = 0;
            for (int j = 0; j < i; j++) {
                if (chars[j] != target) {
                    cost += j + 1;
                    // 反转 [0, j]
                    for (int k = 0; k <= j; k++) {
                        chars[k] = (chars[k] == '0') ? '1' : '0';
                    }
                }
            }
            prefix[i] = cost;
            // 恢复字符串
            for (int j = 0; j < i; j++) {
                if (chars[j] != target) {
                    for (int k = 0; k <= j; k++) {
                        chars[k] = (chars[k] == '0') ? '1' : '0';
                    }
                }
            }
        }
        
        // 计算每个位置的后缀成本
        for (int i = 0; i < n; i++) {
            char target = chars[i];
            long cost = 0;
            for (int j = n - 1; j > i; j--) {
                if (chars[j] != target) {
                    cost += n - j;
                    // 反转 [j, n-1]
                    for (int k = j; k < n; k++) {
                        chars[k] = (chars[k] == '0') ? '1' : '0';
                    }
                }
            }
            suffix[i] = cost;
            // 恢复字符串
            for (int j = n - 1; j > i; j--) {
                if (chars[j] != target) {
                    for (int k = j; k < n; k++) {
                        chars[k] = (chars[k] == '0') ? '1' : '0';
                    }
                }
            }
        }
        
        long result = long.MaxValue;
        for (int i = 0; i < n; i++) {
            result = Math.Min(result, prefix[i] + suffix[i]);
        }
        
        return result;
    }
}

var minimumCost = function(s) {
    const n = s.length;
    if (n === 1) return 0;
    
    let cost = 0;
    
    for (let i = 0; i < n - 1; i++) {
        if (s[i] !== s[i + 1]) {
            cost += Math.min(i + 1, n - i - 1);
        }
    }
    
    return cost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³) - 外层枚举 n 个位置，内层处理前缀/后缀各需要 O(n²) 时间
空间复杂度O(n) - 需要额外的 prefix 和 suffix 数组存储结果

相关题目