[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; }
题解 文章被收录于专栏
主要写一些题目的题解