題目描述
給定一個字符串 s，僅含 0, 1, ? 三種字符，你必須將所有?? 替換為 1 或 0 。
定義 s 的美好值為將所有?進行替換后，s的最長連續 1?或 0?的子串的長度。請你進行所有替換后，使得字符串 s?的美好值最大，請輸出這個美好值。
輸入描述:
本題包含多組數據第一行包含一個正整數 ，表示測試數據組數。對于每組數據：第一行包含一個正整數 ，表示字符串 sss 的長度。接下來一行一個字符串 s，描述如題目所示，。數據保證 。
輸出描述:
對于每組數據：輸出一行一個整數，代表字符串 s 的最大美好值。
鏈接：登錄—專業IT筆試面試備考平臺_牛客網
來源：牛客網
?
示例1
輸入
5
5
01110
1
0
4
01??
3
110
3
1??輸出
3
1
3
2
3
思路：
這個題目也比較的簡單，我們將其中的？全部轉化成1和全部轉化成0分別O(n)遍歷找最長連續序列就可以
AC代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
void solve(){int n;cin >> n;string s;cin >> s;string s1 = s,s2 = s;for(int i = 0;i < n;i++){if(s[i] == '?'){s1[i] = '0';s2[i] = '1';}}int maxx = 0;int cnt = 1;for(int i = 1;i < n;i++){if(s1[i] == s1[i - 1]){cnt++;}else{maxx = max(maxx,cnt);cnt = 1;}}maxx = max(maxx,cnt);cnt = 1;for(int i = 1;i < n;i++){if(s2[i] == s2[i - 1]){cnt++;}else{maxx = max(maxx,cnt);cnt = 1;}}maxx = max(maxx,cnt);cout << maxx << "\n";
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T--){solve();}return 0;
}
)
