同学录网站建设/信阳seo推广

前言

$tag:$ 滑动窗口 暴力

传送门 :
好久没有写滑动窗口了,卡了好久

题意 :
给定一个字符串,让你修改其中的?变为其他大写字符。

使得该字符串存在一个长度为26的子串并且其中每个字符只出现一次

思路 :
很显然的滑动窗口题,至于暴力我没一眼看出来

我们需要维护一个长度为26的不存在重复的字符串

因此我们可以利用滑动窗口维护一个不重复的窗口。我们利用$cnt[]$进行计数,如果当前的窗口出现重复我们移动即可

否则的话,当窗口第一次到达$26$长度的时候,我们就可以进行更改

除了当前26长度的?,我们统一替换为A即可

code :

string s;
int cnt[36];void solve(){cin>>s;int len = s.size();int flag =0  ;for(int i=0,j = 0 ;i< len ;i ++ ){int x;if(s[i]!='?') x = s[i] - 'A';else x = -1;cnt[x]++;while(j<i && cnt[x] > 1 && x!=-1){cnt[s[j] - 'A'] -- ;j++;}//找到的没有重复的窗口if(i-j+1 == 26){//	YES	// cout<<i<<" "<<j<<endl;for(int tp = j ; tp <= i ; tp ++ ){//遍历26的窗口if(s[tp] == '?'){for(int k1 = 0;k1<=25;k1++){//寻找没有用到的单词if(cnt[k1] == 0 ){s[tp] = k1+'A';cnt[k1] ++ ;break;}}}}flag = 1;break;//显然 我们只需要判断一次}}	if(!flag) cout<<-1<<endl;else {for(int i= 0 ; i<len ; i ++ ){if(s[i] == '?')s[i] = 'A';//将26窗口外的? 全替换为A}cout<<s<<endl;}}