class Solution {
public:
int minFlips(string s) {
}
};
1888. 使二进制字符串字符交替的最少反转次数
给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
s 的第一个字符并将它 添加 到字符串结尾。s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。
我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
"010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。
示例 1：
输入：s = "111000" 输出：2 解释：执行第一种操作两次，得到 s = "100011" 。 然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。
示例 2：
输入：s = "010" 输出：0 解释：字符串已经是交替的。
示例 3：
输入：s = "1110" 输出：1 解释：对第二个字符执行第二种操作，得到 s = "1010" 。
提示：
1 <= s.length <= 105s[i] 要么是 '0' ，要么是 '1' 。原站题解
cpp 解法, 执行用时: 304 ms, 内存消耗: 113.1 MB, 提交时间: 2023-09-24 23:19:53
class Solution {
public:
int minFlips(string s) {
// 示性函数
auto I = [](char ch, int x) -> int {
return ch - '0' == x;
};
int n = s.size();
vector<vector<int>> pre(n, vector<int>(2));
// 注意 i=0 的边界情况
for (int i = 0; i < n; ++i) {
pre[i][0] = (i == 0 ? 0 : pre[i - 1][1]) + I(s[i], 1);
pre[i][1] = (i == 0 ? 0 : pre[i - 1][0]) + I(s[i], 0);
}
int ans = min(pre[n - 1][0], pre[n - 1][1]);
if (n % 2 == 1) {
// 如果 n 是奇数，还需要求出 suf
vector<vector<int>> suf(n, vector<int>(2));
// 注意 i=n-1 的边界情况
for (int i = n - 1; i >= 0; --i) {
suf[i][0] = (i == n - 1 ? 0 : suf[i + 1][1]) + I(s[i], 1);
suf[i][1] = (i == n - 1 ? 0 : suf[i + 1][0]) + I(s[i], 0);
}
for (int i = 0; i + 1 < n; ++i) {
ans = min(ans, pre[i][0] + suf[i + 1][0]);
ans = min(ans, pre[i][1] + suf[i + 1][1]);
}
}
return ans;
}
};
python3 解法, 执行用时: 1176 ms, 内存消耗: 45.5 MB, 提交时间: 2023-09-24 23:19:23
class Solution:
def minFlips(self, s: str) -> int:
# 示性函数
I = lambda ch, x: int(ord(ch) - ord("0") == x)
n = len(s)
pre = [[0, 0] for _ in range(n)]
# 注意 i=0 的边界情况
for i in range(n):
pre[i][0] = (0 if i == 0 else pre[i - 1][1]) + I(s[i], 1)
pre[i][1] = (0 if i == 0 else pre[i - 1][0]) + I(s[i], 0)
ans = min(pre[n - 1][0], pre[n - 1][1])
if n % 2 == 1:
# 如果 n 是奇数，还需要求出 suf
suf = [[0, 0] for _ in range(n)]
# 注意 i=n-1 的边界情况
for i in range(n - 1, -1, -1):
suf[i][0] = (0 if i == n - 1 else suf[i + 1][1]) + I(s[i], 1)
suf[i][1] = (0 if i == n - 1 else suf[i + 1][0]) + I(s[i], 0)
for i in range(n - 1):
ans = min(ans, pre[i][0] + suf[i + 1][0])
ans = min(ans, pre[i][1] + suf[i + 1][1])
return ans
golang 解法, 执行用时: 8 ms, 内存消耗: 7.1 MB, 提交时间: 2023-09-24 23:18:59
func minFlips(s string) int {
n := len(s)
ans := n
// 枚举开头是 0 还是 1
for head := byte('0'); head <= '1'; head++ {
// 左边每个位置的不同字母个数
leftDiff := make([]int, n)
diff := 0
for i := range s {
if s[i] != head^byte(i&1) {
diff++
}
leftDiff[i] = diff
}
// 右边每个位置的不同字母个数
tail := head ^ 1
diff = 0
for i := n - 1; i >= 0; i-- {
// 左边+右边即为整个字符串的不同字母个数，取最小值
ans = min(ans, leftDiff[i]+diff)
if s[i] != tail^byte((n-1-i)&1) {
diff++
}
}
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}