滑动窗口：寻找字母。c++

科技前沿 • 2025-03-18 13:36 • 阅读 42

大家好，我是讯享网，很高兴认识大家。

寻找字母字符串

现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。现在问你是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求：如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！

例如

AB??EFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ ABDCEFGHIJKLMNOPQRSTUVWXYZ

讯享网

两种填法都可以构成26个字母，但是题目要求字典序最小，所以输出前者是正确的。
注意：题目要求的是第一个出现的，字典序最小的

输入只有一行，一个符合题目描述的字符串

输出只有一行，如果存在这样的字串，请输出，否则输出-1

讯享网

数据说明
数据点、字符串长度
----- | -----
1,2,3 | 26
4,5,6 | 10⁴
7,8,9,10 | 10⁶

思路：

利用滑动窗口的思想，左边界为L,右边界为R，对字符串从左到右进行扫描
记录每一次窗口中的字符，通过移动有边界来对字母进行判断
如果是问号，就将问号数量增加，如果是字母就判断字母是否存在
如果对应字母已经存在，左边界向左移动到出现R对应的字母的下一个位置并继续处理
如果对应字母不存在那就使用bool型数组进行标记
完成搜索后判断是否？的数量能满足缺少字母的数量，如果成功即可输出对应字符串

讯享网#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int N=1e5; string str; int a[26]; bool test(int i) { 
    memset(a,0,sizeof(a)); int m=0,n=0; for(int j=i;j<i+26;j++) { 
    if(str[j]!='?') { 
    m=str[j]-'A'; a[m]++; if(a[m]>1) return false; } else n++; } return true; } int main() { 
    cin>>str; if(str.size()<26) cout<<"-1"<<endl; else { 
    int len=str.size(); for(int i=0;i<len-25;i++) { 
    if(test(i)) { 
    string s(26,'A'); int m=0; for(int j=i;j<i+26;j++) { 
    if(str[j]=='?') { 
    while(a[m]) m++; s[j-i]='A'+m; a[m]++; } else s[j-i]=str[j]; } cout<<s; return 0; } } cout<<"-1"<<endl; } return 0; }

滑动窗口：寻找字母。c++

相关推荐