Solutions CS101

Appearance

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

greedy,dp, 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 <= 10^5
  • s[i] 为 '0' 或 '1'

下面给出一种贪心思路，其核心在于观察字符串相邻字符发生变化的“边界”。
关键观察
对于相邻两个字符不同的位置（记为下标 i 与 i+1 之间的边界），必然需要一次反转操作来消除这个不连续。

  • 如果对前缀进行反转，恰好反转到下标 i，则该操作成本为 i+1；
  • 如果对后缀进行反转，从下标 i+1 开始，则成本为 n – (i+1)；
    为了降低成本，对于每个边界，我们都可以选择成本较小的那种操作，即：

cost_boundary = min(i+1, n - (i+1))

因此，所有边界的成本之和即为将字符串变成全 0 或全 1 的最小成本。

注意

  • 当字符串已经全相同时，边界数为 0，成本自然为 0。
  • 对于示例 "0011"，只有一个边界（下标 1 与 2之间），成本为 min(2, 2)=2；
  • 对于示例 "010101"，边界分别出现在下标 0、1、2、3、4处，总成本为 1+2+3+2+1=9。

下面给出 Python 代码实现：

python
class Solution:
    def minimumCost(self, s: str) -> int:
        n = len(s)
        total_cost = 0
        # 遍历每个相邻字符，若不同则产生一个“边界”
        for i in range(n - 1):
            if s[i] != s[i+1]:
                total_cost += min(i + 1, n - (i + 1))
        return total_cost

代码说明

  • 遍历字符串：对于每个下标 i（从 0 到 n-2），检查 s[i] 与 s[i+1] 是否不同。
  • 累加成本：如果不同，就累加 min(i+1, n-(i+1))。这正好对应两种反转操作中成本较小的那一个。
  • 返回结果：最终返回所有边界累加起来的最小成本。

这种方法时间复杂度为 O(n) ，能够处理 n 到 10^5 的情况。