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

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

给你一个下标从 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'

解题思路

1.遍历每个字符，考虑从头到当前元素，从尾到前当前元素，变成0 或者1所操作的次数。
2.用两个数组arr1,arr2分别记录从尾到i时， 全都变成0 或者全都变成1所使用的操作次数。
3.从前往后遍历，用两个变量a， b记录 从头到当前元素全都变成0 或者全都变成1所使用的操作次数。
4.最小操作次数为： max = Math.min(max, Math.min(a + arr0[i], b + arr1[i]));

class Solution {

    public long minimumCost(String s) {
        char[] chars = s.toCharArray();
        int length = s.length();
        long[] arr0 = new long[length];
        long[] arr1 = new long[length];
        if (chars[length - 1] == '0') {
            arr1[length - 1] = 1;
        } else {
            arr0[length - 1] = 1;
        }
        for (int i = length - 2; i >= 0; i--) {
            if (chars[i] == '0') {
                arr0[i] = arr0[i + 1];
                arr1[i] = arr0[i + 1] + length - i;
            } else {
                arr1[i] = arr1[i + 1];
                arr0[i] = arr1[i + 1] + length - i;
            }
        }
        long a = 0;
        long b = 0;
        long max = Math.min(arr0[0], arr1[0]);
        for (int i = 0; i < length; i++) {
            max = Math.min(max, Math.min(a + arr0[i], b + arr1[i]));
            if (chars[i] == '0') {
                b = (i + 1 + a);
            } else {
                a = (i + 1 + b);
            }
        }
        return Math.min(max, Math.min(a, b));
    }
}

 勉强能过。。