网站的版式,网站开发设计师薪资,wordpress投票插件,公司网站免费自建题目描述
给定一个字符串 s#xff0c;仅含 0, 1, ? 三种字符#xff0c;你必须将所有 ? 替换为 1 或 0 。 定义 s 的美好值为将所有?进行替换后#xff0c;s的最长连续 1 或 0 的子串的长度。请你进行所有替换后#xff0c;使得字符串 s 的美好值最大#xff0c;请输…题目描述
给定一个字符串 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代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e510;
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;
}
