尺取法
方格取数
https://ac.nowcoder.com/acm/problem/16759
天哪,第一次接触到尺取法真的有点菜了
数据10e6 dp肯定不行,而且要拿一层for循环搞定
参考大佬的,又涨知识了 取连续段这种问题,即区间问题
就可以考虑用各种区间解法就可以考虑用各种区间解法
线段树,树状数组,前缀和尺取线段树,树状数组,前缀和尺取
这句话真的是精髓 双指针,看区间内是否有26种字母,如果满足
记录答案,使答案最小化,并且左指针移动记录答案,使答案最小化,并且左指针移动
不满足就让右指针右移看更长的区间是否满足不满足就让右指针右移看更长的区间是否满足
我的代码
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1000000+7; char s[maxn]; int vis[300]; // 记录字母的数组 const int inf=0x3f3f3f3f; int check(){ //检查是否含有26个字母 for(int i=0;i<26;i++){ if(!vis[i])return 0; } return 1; } int main(){ scanf("%s",s); int l=1; int lens=strlen(s); int ans=inf; for(int r=1;r<=lens;r++){ //尺取法 vis[s[r]-'a']++; while(check()){ ans=min(ans,r-l+1); //如果成功了记录值 vis[s[l]-'a']--;l++; // 并将左指针向右移动 } } printf("%d\n",ans); return 0; }
加油~