[NC18386]字符串

字符串

https://ac.nowcoder.com/acm/problem/18386

题解:
尺取法,因为这个题目让你找包含26个字母且长度最小的连续区间,所以我们考虑双指针这种算法,从左边往右边移动,每次判断一下确定的区间是否符合标准
1.如果符合标准的话,那么我们让左指针往右边移动,同时对应的删除左指针移动走的拿个字符。
2.如果不符合标注,那么我们需要让区间继续扩大,也就是让右指针往右移动,同时添加上我们新纳入这个区间的字符。
那么我们该如何判断这个区间是否符合标准呢?我们可以用一个数组来记录相应字母的出现次数即可,每次遍历一下这个数组看看是否每个字符都至少出现过一次。
代码:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 200;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
string s;
int visited[maxn];
int main(){
    cin>>s;
    memset(visited,0,sizeof(visited));
    int l=0,r=0,ans=MaxN,len=s.size();
    while (true){
        bool flag=true;
        for(int i=0;i<26;i++){
            if(visited[i]==0){
                flag=false;
                break;
            }
        }
        if(flag){
            ans=min(ans,r-l+1);
            l++;
            visited[s[l-1]-'a']--;
        } else{
            r++;
            if(r==len) break;
            visited[s[r]-'a']++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
题解 文章被收录于专栏

主要写一些题目的题解

全部评论

相关推荐

孤寡孤寡的牛牛很热情:为什么我2本9硕投了很多,都是简历或者挂,难道那个恶心人的测评真的得认真做吗
点赞 评论 收藏
分享
一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务