给你一个下标从 0 开始、长度为 n 的二进制字符串 s ,你可以对其执行两种操作: 选中一个下标 i 并且反转从下标 0 到下标 i(包括下标 0 和下标 i )的所有字符,成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1(包括下标 i 和下标 n - 1 )的所有字符,成本为 n - i 。 返回使字符串内所有字符 相等 需要的 最小成本 。 反转 字符意味着:如果原来的值是 '0' ,则反转后值变为 '1' ,反之亦然。用Java解决
时间: 2024-02-13 07:05:27 浏览: 107
可以使用贪心算法解决这个问题。
首先统计字符串中 0 和 1 的数量,如果两者数量相等,那么所有字符都可以变成其中任意一个字符,成本为 0。
如果两者数量不相等,那么我们需要将其中数量多的字符变成数量少的字符。我们可以假设将所有的 0 都变成 1,然后统计从左到右变成 1 时的成本,然后假设将所有的 1 都变成 0,统计从右到左变成 0 时的成本,两者取最小值即为最终成本。
具体实现可以参考以下代码:
```java
public 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 cost1 = 0, cost2 = 0, res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
cost1 += (i + 1);
cnt0--;
} else {
cost2 += (n - i);
cnt1--;
}
if (cnt0 == 0 || cnt1 == 0) {
res = Math.min(res, Math.min(cost1, cost2));
break;
}
}
return res;
}
```
阅读全文