给你一个下标从 0 开始、长度为 n 的二进制字符串 s ,你可以对其执行两种操作: 选中一个下标 i 并且反转从下标 0 到下标 i(包括下标 0 和下标 i )的所有字符,成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1(包括下标 i 和下标 n - 1 )的所有字符,成本为 n - i 。 返回使字符串内所有字符相等 需要的最小成本和
时间: 2024-02-13 17:04:54 浏览: 73
这道题可以使用数学方法进行求解。
首先,我们统计出字符串中 '0' 和 '1' 的个数。如果其中一个为 0,那么字符串内所有字符已经相等,返回 0 即可。
然后,我们令 cost(i) 表示将字符串的所有字符都变成字符 s[i] 需要的最小成本。我们可以分别计算将左边或者右边的字符反转到当前位置的成本,然后取最小值,得到如下的递推式:
```
cost(i) = min(i+1, n-i) + cost(i-1) + (1 if s[i] != s[i-1] else 0)
```
其中,如果 s[i] != s[i-1],说明我们需要将 s[i] 和 s[i-1] 都变成另一个字符,这样才能使整个字符串中的所有字符都相等。
最后,我们返回 cost(n-1),就是将整个字符串中的所有字符都变成其中一个字符所需要的最小成本。时间复杂度为 O(n)。
下面是 Java 代码实现:
```java
public static int minCost(String s) {
int n = s.length();
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
cnt0++;
} else {
cnt1++;
}
}
if (cnt0 == 0 || cnt1 == 0) {
return 0;
}
int[] cost = new int[n];
cost[0] = 1;
for (int i = 1; i < n; i++) {
cost[i] = Math.min(i+1, n-i) + cost[i-1] + (s.charAt(i) != s.charAt(i-1) ? 1 : 0);
}
return cost[n-1];
}
```
阅读全文