class Solution {
public:
long long minimumCost(string s) {
}
};
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 <= 105s[i] 为 '0' 或 '1'原站题解
python3 解法, 执行用时: 132 ms, 内存消耗: 16.6 MB, 提交时间: 2023-05-31 15:23:45
# 贪心思路，中间向两边数
class Solution:
def minimumCost(self, s: str) -> int:
n, ans = len(s), 0
pre, cnt = s[n >> 1], 0
for l in range((n >> 1) - 1, -1, -1):
if s[l] != pre:
cnt += 1
pre = s[l]
ans += cnt
pre, cnt = s[n >> 1], 0
for r in range((n >> 1) + 1, n):
if s[r] != pre:
cnt += 1
pre = s[r]
ans += cnt
return ans
golang 解法, 执行用时: 8 ms, 内存消耗: 6.1 MB, 提交时间: 2023-05-31 15:23:04
func minimumCost(s string) (ans int64) {
n := len(s)
for i := 1; i < n; i++ {
if s[i-1] != s[i] {
ans += int64(min(i, n-i))
}
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 20 ms, 内存消耗: 11.8 MB, 提交时间: 2023-05-31 15:22:49
class Solution {
public:
long long minimumCost(string s) {
long long ans = 0;
int n = s.length();
for (int i = 1; i < n; i++)
if (s[i - 1] != s[i])
ans += min(i, n - i);
return ans;
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 43.1 MB, 提交时间: 2023-05-31 15:22:35
class Solution {
public long minimumCost(String S) {
long ans = 0;
char[] s = S.toCharArray();
int n = s.length;
for (int i = 1; i < n; i++)
if (s[i - 1] != s[i])
ans += Math.min(i, n - i);
return ans;
}
}
python3 解法, 执行用时: 168 ms, 内存消耗: 16.8 MB, 提交时间: 2023-05-31 15:22:22
class Solution:
def minimumCost(self, s: str) -> int:
return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)