LeetCode 1888 使二进制字符串交替的最少反转次数
🟠 中等偏上
朴素思路
枚举拼接位置，对拼接后的字符串检查转为 ‘01’ 或 ‘10’ 。时间复杂度 O(n*n) 。
class Solution {
public:
int minFlips(string s) {
int res = s.size();
for(int len = 0;len<s.size();len++){
string pre_s = s.substr(0,len);
string ss = s.substr(len,s.size()-len+1)+pre_s;
// 01
int count_1 = 0;
for(int i = 0;i<s.size();i++){
if(i%2==0&&ss[i]!='0') count_1++;
if(i%2==1&&ss[i]!='1') count_1++;
}
// 10
int count_2 = 0;
for(int i = 0;i<s.size();i++){
if(i%2==0&&ss[i]!='1') count_2++;
if(i%2==1&&ss[i]!='0') count_2++;
}
res = min(res,min(count_1,count_2));
}
return res;
}
};
O(n) 思路
拼接有如下几种
这种拼接是 前面的一节 和从后往前的一截进行拼接，经典两次遍历
0101 10101 -> 01101 0101
1010 01010 ->
第一段的开头和第二段的末尾分别是 0 1或 1 0，
因此，设置两个数组pre_1 last_0记录 以1开头到index的（使之变为01交替）反转次数，以末尾0向前到index （使之变为01交替）的反转次数。
class Solution {
public:
int minFlips(string s) {
vector<int> pre_1(s.size()+1,0); // pre_1[i] -> 包含 i-1; 包含 i -> pre_1[i+1]
vector<int> pre_0(s.size()+1,0);
vector<int> last_0(s.size()+1,0); //last_0[i] -> 包含i
vector<int> last_1(s.size()+1,0);
for(int i = 0;i<s.size();i++){
pre_0[i+1] = pre_0[i];
if(i%2==0&&s[i]!='0') pre_0[i+1]++;
if(i%2==1&&s[i]!='1') pre_0[i+1]++;
pre_1[i+1] = pre_1[i];
if(i%2==0&&s[i]!='1') pre_1[i+1]++;
if(i%2==1&&s[i]!='0') pre_1[i+1]++;
}
int dao_yi = (s.size()-1)%2;
int dao_er = dao_yi==0?1:0;
for(int i=s.size()-1;i>=0;i--){
last_0[i] = last_0[i+1];
if(i%2==dao_yi&&s[i]!='0') last_0[i]++;
if(i%2==dao_er&&s[i]!='1') last_0[i]++;
last_1[i] = last_1[i+1];
if(i%2==dao_yi&&s[i]!='1') last_1[i]++;
if(i%2==dao_er&&s[i]!='0') last_1[i]++;
}
int res = s.size();
for(int i = 0;i<s.size();i++){
res = min(res,pre_0[i+1]+last_1[i+1]);
res = min(res,pre_1[i+1]+last_0[i+1]);
}
return res;
}
};
传统滑窗
基于上面的拼接思想，可以直接拼接两个字符串然后滑窗。
一个字符串 改为 ’01‘ 的操作次数位 count 那么改为 ’10‘的操作次数一定是 len-count。
这里使用了 static_cast<int> ，是因为 size() 函数返回无符号数做减法再转为int型可能导致错误。较好的做法是 在一开始就定义 int n = s.size()，后续使用 int型 n。
class Solution {
public:
int minFlips(string s) {
int left = 0;
int res = s.size();
string pattern = "01";
int count = 0;
for(int i = 0;i<=0+static_cast<int>(s.size())-1-1;i++){
count+=s[i]!=pattern[i%2];
}
for(int i = s.size()-1;i<=2*s.size()-1;i++){
count+=s[i%s.size()]!=pattern[i%2];
res = min(res,min(count,static_cast<int>(s.size())-count));
count-=s[i-s.size()+1]!=pattern[(i-s.size()+1)%2];
}
return res;
}
};