题目描述
如何填充这些位置使得这个01串中出现互不重叠的 00 和 11 子串最多,输出子串个数;
样例
输入样例:
1110?0
输出样例:
2
样例解释
如果在问号处填 0,则最多出现一个 00 和一个 11:111000.
解题思路:
字符?出现的位置分两种情况:
1. ?被全是0或全是1包围; 例如: 111?111;000?000;
这种情况下,?只能填充1或0
2. ?左右字符不相等; 例如: 111?000;000?111
这种情况下,?的填充看之前的1或0的数量,如果?前的连续1或0的数量为奇数,则按?之前的字符填充,若是偶数,则按?之后的字符填充;
时间复杂度O(n)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long res=0;
string s;
int p1=0;//遍历区间左指针
cin>>s;
int size = s.length(); //字符串长度
if(size==1){
cout<<0<<endl;
return 0;
}
for(int i=0;i<size;i++){
if(s[i]=='?'){ //检测到字符?
if(i-1>0&&i+1<size){
if(s[i-1]==s[i+1]){ //情况1: 000?000 111?111
if(s[i-1]=='1'){ // 改变字符串
s[i] = '1';
}
else if(s[i-1]=='0'){
s[i] = '0';
}
}
//情况2: 000?111 111?000
else{//判断之前的连续字符长度奇偶性
if((i-p1)%2==1){ //奇数
s[i] = s[i-1];
}
else{
//注意在取s[i+1]之前判断,i+1是否为?
if(s[i+1]!='?'){
s[i] = s[i+1];
}
}
}
}
if(i==0&&s[i+1]!='?'){ //左端为?
s[i] = s[i+1];
}
if(i==size-1&&s[i-1]!='?'){//右端为?
s[i] = s[i-1];
}
}
if(s[i]!=s[p1]){ //计数
res += (i-p1)/2;
p1=i;
}
if(i==size-1){ //最后i到端点计数
res += (size-p1)/2;
}
}
cout<<res<<endl;
return 0;
}