Leetcode 2712. Minimum Cost to Make All Characters Equal

[Woodyiiiiiii]

2712. Minimum Cost to Make All Characters Equal

2712. Minimum Cost to Make All Characters Equal

这种01二字字符串有很多类似题目，因为01的限制，大多情况下可以用动态规划。

类似题目:

• 926. Flip String to Monotone Increasing / 1653. Minimum Deletions to Make String Balanced
• 1653. Minimum Deletions to Make String Balanced

题解：

• 一次遍历，简洁写法（Python/Java/C++/Go）
• 赛事活动｜[第 347 场周赛]式酱的解题报告

一、贪心Greedy

我的做法是，既然要让字符串所有字符相等，那么最后字符串只有两种结果，“00..0”或者"11..1"。那么我就对这两种理想字符串分类讨论，要想达到两种目的字符串，分别计算所花费的最小结果，然后对比。那么如何计算最小花费呢？那就要改变每个不符合要求的字符，同时也要让最后的花费最小——我观察样例后，觉得从中间开始最公平(因为中间要反转字符的话花费是一样的)，然后从两边扩散，反转不符合要求的字符，然后记录翻转次数，与以后的字符对比，来判断要不要反转。

class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        int mid = n / 2;
        long t1 = 0, t2 = 0;
        int sign = 0;   // 0 偶数 1 奇数
        // make 1
        for (int i = mid; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '0' && sign == 0) {
                t1 += (i + 1);
                sign = 1 - sign;
            } else if (c == '1' && sign == 1) {
                t1 += (i + 1);
                sign = 1 - sign;
            }
        }
        sign = 0;
        for (int i = mid + 1; i < n; i++) {
            char c = s.charAt(i);
            if (c == '0' && sign == 0) {
                t1 += (n - i);
                sign = 1 - sign;
            } else if (c == '1' && sign == 1) {
                t1 += (n - i);
                sign = 1 - sign;
            }
        }
        // make 0
        sign = 0;
        for (int i = mid; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '1' && sign == 0) {
                t2 += (i + 1);
                sign = 1 - sign;
            } else if (c == '0' && sign == 1) {
                t2 += (i + 1);
                sign = 1 - sign;
            }
        }
        sign = 0;
        for (int i = mid + 1; i < n; i++) {
            char c = s.charAt(i);
            if (c == '1' && sign == 0) {
                t2 += (n - i);
                sign = 1 - sign;
            } else if (c == '0' && sign == 1) {
                t2 += (n - i);
                sign = 1 - sign;
            }
        }
        return Math.min(t1, t2);
    }
}

二、动态规划DP

当然，正解是动态规划。

首先可以分割成子问题，s[0i]是相等的，s[0i-1]也会是相等的，前者由后者的最小花费得来，因为翻转不改变相邻字符的关系。

class Solution {
    public long minimumCost(String s) {
        long ans = 0;
        char[] cc = s.toCharArray();
        for (int i = 1; i < s.length(); i++) {
            char c = cc[i], pre = cc[i - 1];
            if (c != pre) {
                ans += Math.min(i, s.length() - i);
            }
        }
        return ans;
    }
}