LeetCode 1888. 使二进制字符串字符交替的最少反转次数
原题链接
中等
作者:
ITNXD
,
2021-06-08 10:30:43
,
所有人可见
,
阅读 430
详细请查看注释内容
参考代码:
class Solution {
/*
两种操作顺序互不影响,因此考虑第一种操作结束后的情况:
偶数:(直接枚举)
1010...10
0101...01
res = min(l[0][n - 1], l[1][n - 1]);
奇数:(前两种情况直接枚举)
1010...01
0101...10
res = min(l[0][n - 1], l[1][n - 1]);
(后两种借助预处理前缀和数组解决)
010101... 11 01
101010... 00 10
对于后两种情况可以枚举11和00的位置来进行选择!
我们可以使用前后缀分解思路来预处理几个数组:
l[0][i]:表示[0, i]区间01(从左到右)相间的最少操作次数
l[1][i]:表示[0, i]区间10(从左到右)相间的最少操作次数
r[0][i]:表示[i, 0]区间01(从右到左)相间的最少操作次数
r[1][i]:表示[i, 0]区间10(从右到左)相间的最少操作次数
因此后两种情况最终答案就是:res = min(res, l[0][i] + r[1][i + 1], l[1][i] + r[0][i + 1]);
*/
public:
int minFlips(string s) {
int n = s.size();
vector<int> l[2], r[2];
l[0] = l[1] = r[0] = r[1] = vector<int>(n);
// 预处理l[0][i],l[1][i]
for(int i = 0; i < 2; i ++)
for(int j = 0, c = 0, k = i; j < n; j ++, k ^= 1){
if(k != s[j] - '0') c ++;
l[i][j] = c;
}
// 预处理r[0][i],r[1][i]
for(int i = 0; i < 2; i ++)
for(int j = n - 1, c = 0, k = i; j >= 0; j --, k ^= 1){
if(k != s[j] - '0') c ++;
r[i][j] = c;
}
// 偶数的两种情况的最小值
if(n % 2 == 0) return min(l[0][n - 1], l[1][n - 1]);
else {
// 奇数的前两种情况
int res = min(l[0][n - 1], l[1][n - 1]);
// 枚举11或00出现位置
for(int i = 0; i + 1 < n; i ++){
res = min(res, l[0][i] + r[1][i + 1]);
res = min(res, l[1][i] + r[0][i + 1]);
}
return res;
}
}
};
r[0][i]:表示[i, 0]区间01(从右到左)相间的最少操作次数
r[1][i]:表示[i, 0]区间10(从右到左)相间的最少操作次数
我没看懂, 是不是搞反了,
r[0][i]:表示[n-1, i]区间01(从右到左)相间的最少操作次数
r[1][i]:表示[n-1, i]区间10(从右到左)相间的最少操作次数