CodeForces 701C They Are Everywhere (滑动窗口)

题目链接:http://codeforces.com/problemset/problem/701/C

题意:找到字符串中能包含所有元素的最短字符串长度。

利用“滑动窗口”解题

解题思路:

1. 遍历找到所有元素进行统计,元素数sum

2.设置两个”指针“ st、en,双重while 循环

3.先清空dp[]数组,进行统计

双重while

第一个 whielt(st<n)

{

  内部while(en<n&&sum!=sum1)//sum1统计元素个数

  {//内部while

    sum1 统计

    dp[s[en]]++ 每个元素出现的次数统计

    en++

  }

  如果sum==sum1 找到小值 ans=min(ans,en-st);

  *如果--dp[s[st]]==0,则说明 s[st] 这个元素在统计的所有元素个数中没有了,此时sum1--,即应重新统计s[st]  这个元素,以确保长度包含所有元素。【关键点】

  st++;

}

输出 asn 即可。

//16.09.07 22:10

看博再次看到滑动窗口,觉得解释的不算清晰,特补充解释下:

AC code:

 #include<bits/stdc++.h>
using namespace std;
int dp[];
int main()
{
int n;
string s;
while(~scanf("%d",&n))
{
cin>>s;
int sum=;
memset(dp,,sizeof(dp));
for(int i=; i<n; i++)
{
if(!dp[s[i]])
{
dp[s[i]]=;
++sum;
}
}
int st,en,sum1,ans;
st=en=sum1=;
ans=<<;
memset(dp,,sizeof(dp));
while(st<n)
{
while(en<n&&sum!=sum1)
{
if(dp[s[en]]==)
{
sum1++;
}
dp[s[en++]]++;
}
if(sum==sum1)ans=min(ans,en-st);
if(--dp[s[st++]]==)sum1--;
}
cout<<ans<<endl;
}
return ;
}
上一篇:[Flex] PopUpButton系列 —— 将DataGrid作为弹出内容


下一篇:Java学习之反射篇