使所有字符相等的最小成本
难度:
标签:
题目描述
You are given a 0-indexed binary string s of length n on which you can apply two types of operations:
- Choose an index
iand invert all characters from index0to indexi(both inclusive), with a cost ofi + 1 - Choose an index
iand invert all characters from indexito indexn - 1(both inclusive), with a cost ofn - i
Return the minimum cost to make all characters of the string equal.
Invert a character means if its value is '0' it becomes '1' and vice-versa.
Example 1:
Input: s = "0011" Output: 2 Explanation: Apply the second operation withi = 2to obtains = "0000" for a cost of 2. It can be shown that 2 is the minimum cost to make all characters equal.
Example 2:
Input: s = "010101" Output: 9 Explanation: Apply the first operation with i = 2 to obtain s = "101101" for a cost of 3. Apply the first operation with i = 1 to obtain s = "011101" for a cost of 2. Apply the first operation with i = 0 to obtain s = "111101" for a cost of 1. Apply the second operation with i = 4 to obtain s = "111110" for a cost of 2. Apply the second operation with i = 5 to obtain s = "111111" for a cost of 1. The total cost to make all characters equal is 9. It can be shown that 9 is the minimum cost to make all characters equal.
Constraints:
1 <= s.length == n <= 105s[i]is either'0'or'1'
代码结果
运行时间: 94 ms, 内存: 16.5 MB
/*
* 思路：
* 使用Java Stream API，我们可以简化代码。通过流的操作来计算不同的反转成本。
* 我们仍然需要计算将所有字符变为 '0' 或 '1' 的最小成本。
*/
import java.util.stream.IntStream;
public class MinCostStream {
public int minCost(String s) {
int n = s.length();
int[] costsForZero = new int[n];
int[] costsForOne = new int[n];
IntStream.range(0, n).forEach(i -> {
costsForZero[i] = s.charAt(i) == '1' ? i : 0;
costsForOne[i] = s.charAt(i) == '0' ? i : 0;
});
int totalCostForAllToZero = IntStream.of(costsForZero).sum();
int totalCostForAllToOne = IntStream.of(costsForOne).sum();
return Math.min(totalCostForAllToZero, totalCostForAllToOne);
}
}解释
方法:
此题解的思路是将字符串分为左右两部分进行处理。对于每一部分，遍历字符串，比较相邻字符是否相等。如果不相等，就累加当前下标作为成本。对于长度为奇数的字符串，中间的字符需要特殊处理。最后将所有成本累加得到最小成本。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在处理长度为奇数的字符串时，中间的字符需要特殊处理？
▷🦆
题解中提到的将字符串分为左右两部分处理，具体是如何定义这两部分的？
▷🦆
在计算成本时，累加当前下标的方式是否确实能代表实际操作的成本？
▷🦆
为什么在遍历字符串比较相邻字符的时候，仅通过增加下标值来计算成本？
▷