东莞制作网站的联系方式,官网模板免费下载,推进网站集约化建设,青岛学网站建设的大学题干#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld
题目描述
小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的#xff0c;当且仅…题干
时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld
题目描述
小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中长度最短是多少。
输入描述:
一行一个字符串S。只包含小写字母。S的长度不超过106.
输出描述:
一行一个数字代表最短长度。数据保证存在一个合法的S的子串。 示例1
输入
复制
ykjygvedtysvyymzfizzwkjamefxjnrnphqwnfhrnbhwjhqcgqnplodeestu
输出
复制
49
解题报告 尺取或者更新最后一次出现的坐标也可以我叫他桶标记法类似的题目HDU 3333 SPOJ DQUERY
错误代码
#includebits/stdc.husing namespace std;
char s[1000005];
int vis[30];
int main()
{scanf(%s,s);int len strlen(s);memset(vis,0,sizeof vis);int l 0,r 0,cnt 0,minn 0x3f3f3f3f;while(rlen) {if(vis[s[r]-a] 0) {cnt;}vis[s[r]-a];if(cnt 26) break;r;}while(r len) {vis[s[r]-a];while(vis[s[l] - a] 1) {vis[s[l] - a]--;l;}minn min(minn,r-l1);r;//先更新minn再更新r}printf(%d\n,minn);return 0 ;}
// qwertyuioplkjhgfdsazxcvbnm
总结 刚开始自己写的这个代码有点想少了本来是想都放在一个while中的但是感觉这样逻辑结构不是很清晰然后就想把它新开一个while放进去但是在边界处理的时候出现了问题那就是我没有我在cnt26的时候break了但是r这步没有执行然后进入第二个while又vis了一次也就是说同一个s[r]我们在vis数组中计算了两次。 而你不能直接把r放到if(cnt 26) break;前面因为这样的话出现的第二个问题就是比如你输入aaaabcdefg....xyz那么扫到最后一个字符rbreak。然后就进不去下面的while循环了、、因为这时的rlen所以进不去这个循环l就没法前移就找不到最短的解于是会wa。
AC代码1自己写 有点麻烦了
#includebits/stdc.husing namespace std;
char s[1000005];
int vis[30];
int main()
{scanf(%s,s);int len strlen(s);memset(vis,0,sizeof vis);int l 0,r 0,cnt 0,minn 0x3f3f3f3f;while(rlen) {if(vis[s[r]-a] 0) cnt;vis[s[r]-a];if(cnt 26) break;r;}while(vis[s[l] - a] 1) {vis[s[l] - a]--;l;}minn min(minn,r-l1);r;while(r len) {vis[s[r]-a];while(vis[s[l] - a] 1) {vis[s[l] - a]--;l;}minn min(minn,r-l1);r;//先更新minn再更新r } printf(%d\n,minn);return 0 ;}
// qwertyuioplkjhgfdsazxcvbnm
AC代码2在线更新坐标的思想
#include iostream
#include cstdio
#include algorithm
#include cstdlib
#include cstring
#include string
#include deque
#include set
#include queue
using namespace std;
#define ll long long
#define N 1000009
#define gep(i,a,b) for(int ia;ib;i)
#define gepp(i,a,b) for(int ia;ib;i--)
#define gep1(i,a,b) for(ll ia;ib;i)
#define gepp1(i,a,b) for(ll ia;ib;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define P pairint,intu
char s[N];
int loc[30];
int main()
{scanf(%s,s);int l0;int lenstrlen(s);int anslen1;mem(loc,-1);int cnt0;//只要[l,i]区间里含有26个字母即可gep(i,0,len-1){if(loc[s[i]-a]-1){cnt;} loc[s[i]-a]i;//该字母最大的坐标while(lloc[s[l]-a]) l;//后面有了那么前面的就可以不用了l。减小去区间长度if(cnt26){ansmin(ans,i-l1);}}printf(%d\n,ans);return 0;
} AC代码3
#include bits/stdc.h
#define N 1000010
#define INF 0x3f3f3f3f
using namespace std;int main()
{int i,l0,ansINF;int vis[200]{0};string s;setcharmyset;cins;for(i0;s[i];i){myset.insert(s[i]);vis[s[i]];while(vis[s[l]]1)vis[s[l]]--,l;if(myset.size()26)ansmin(ans,i-l1);}coutansendl;return 0;
}
