给你一个下标从 0 开始、长度为 n 的二进制字符串 s ,你可以对其执行两种操作: 选中一个下标 i 并且反转从下标 0 到下标 i(包括下标 0 和下标 i )的所有字符,成本为 i + 1 。 选中一个下标 i 并且反转从下标 i 到下标 n - 1(包括下标 i 和下标 n - 1 )的所有字符,成本为 n - i 。 返回使字符串内所有字符 相等 需要的 最小成本 。
时间: 2024-02-13 22:04:51 浏览: 155
将字符串反转
这是一道比较经典的字符串问题,可以使用贪心算法求解。首先我们要找到字符串中出现次数最多的字符,然后将其它字符全部转换成该字符。因为每次操作都是将一段字符全部反转,所以我们可以先考虑将字符串变成该字符的形式,然后再通过一些操作将其全部变成相等的字符。
具体做法如下:首先统计字符串中每个字符出现的次数,找到出现次数最多的字符,设为 c。然后计算将整个字符串变成 c 的代价 cost1,即将所有不等于 c 的字符全部反转成 c 的代价。接下来考虑将字符串从中间切开,将前半部分反转成 c 的代价 cost2 和将后半部分反转成 c 的代价 cost3。最后取这三种操作的最小值即为所求。具体实现可以参考以下代码:
```python
def minCost(s: str) -> int:
n = len(s)
cnt = [0] * 2
for c in s:
cnt[ord(c) - ord('0')] += 1
if cnt[0] == n or cnt[1] == n:
return 0
c = '0' if cnt[0] > cnt[1] else '1'
cost1 = n - cnt[ord(c) - ord('0')]
cost2 = cost3 = float('inf')
s1 = s[:n//2]
s2 = s[n//2:]
if len(s1) > 0 and s1[-1] != c:
cost2 = n//2 - s1.count(c)
if len(s2) > 0 and s2[0] != c:
cost3 = n//2 - s2.count(c)
return min(cost1, cost2+cost1, cost3+cost1)
```
注意,在切分字符串时,需要将字符串切分成两部分,并且要注意中间位置的字符,因为该字符会被分到两个部分中。
阅读全文