[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;
}
题解 文章被收录于专栏

主要写一些题目的题解

全部评论

相关推荐

11-04 21:17
江南大学 Java
穷哥们想卷进大厂:肯定会问技术呀,面试你的可能是别人
点赞 评论 收藏
分享
11-09 01:22
已编辑
东南大学 Java
高级特工穿山甲:羡慕,我秋招有家企业在茶馆组织线下面试,约我过去“喝茶详谈”😢结果我去了发现原来是人家喝茶我看着
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务