首页 > 代码库 > UVA - 10815 Andy's First Dictionary
UVA - 10815 Andy's First Dictionary
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18649
给你一段不超过5000行的文本,让你从中找出所有的单词,并且按照字典序排序,注意不区分大小写。
题目意思还是很好懂的,但是开始误认为单词总数不超过5000,但是还有很多重复的,于是不幸的run error,所以数组最少需要开到10万去,并且普通排序是必然超时的!这里用qsort。
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; char str[100200][210]; int cmp(const void* s1,const void* s2) { return strcmp((char*)s1,(char*)s2); } int main() { freopen("a.txt","r",stdin); char s[210],ss[210]; int i,j,k=0; while(gets(s)) { memset(ss,'\0',sizeof(ss)); j=0; int l=strlen(s); for(i=0;i<l;i++) { if(s[i]>='A'&&s[i]<='Z') //把大写字母转化成小写字母 { s[i]+=32; } if(s[i]>='a'&&s[i]<='z') { ss[j++]=s[i]; //保存单词 } if(j) //必须是单词才能下一步, { if((i==l-1)||(!(s[i]>='a'&&s[i]<='z'))) { strcpy(str[k++],ss); //复制单词到数组中 memset(ss,'\0',sizeof(ss)); j=0; } } } } /* for(i=0;i<k;i++) //冒泡超时 { for(j=i+1;j<k;j++) { if(strcmp(str[i],str[j])>0) { memset(ss,'\0',sizeof(ss)); strcpy(ss,str[i]); strcpy(str[i],str[j]); strcpy(str[j],ss); } } }*/ qsort(str,k,sizeof(str[0]),cmp); //排序 printf("%s\n",str[0]); memset(ss,'\0',sizeof(ss)); strcpy(ss,str[0]); for(i=1;i<k;i++) //防止重复 { if(strcmp(str[i],ss)!=0) { printf("%s\n",str[i]); strcpy(ss,str[i]); } else strcpy(ss,str[i]); } return 0; }
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; char str[100200][210]; char *strp[100200]; bool cmp(const char* s1,const char* s2) { return strcmp(s1,s2)<0; } int main() { //freopen("a.txt","r",stdin); char s[210],ss[210]; int i,j,k=0; while(gets(s)) { memset(ss,'\0',sizeof(ss)); j=0; int l=strlen(s); for(i=0;i<l;i++) { if(s[i]>='A'&&s[i]<='Z') //把大写字母转化成小写字母 { s[i]+=32; } if(s[i]>='a'&&s[i]<='z') { ss[j++]=s[i]; //保存单词 } if(j) //必须是单词才能下一步, { if((i==l-1)||(!(s[i]>='a'&&s[i]<='z'))) { strcpy(str[k++],ss); //复制单词到数组中 memset(ss,'\0',sizeof(ss)); j=0; } } } } for(i=0;i<k;i++) { strp[i]=str[i]; } sort(strp,strp+k,cmp); printf("%s\n",strp[0]); memset(ss,'\0',sizeof(ss)); strcpy(ss,strp[0]); for(i=1;i<k;i++) //防止重复 { if(strcmp(strp[i],ss)!=0) { printf("%s\n",strp[i]); strcpy(ss,strp[i]); } else strcpy(ss,strp[i]); } return 0; }
还有一个不用gets的,用getchar读字符,速度远远比gets慢。也可能是判重的影响,
#include<cstdio> #include<ctype.h> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100005; char str[maxn][210]; char *strp[maxn]; bool cmp(const char *s1,const char *s2) { return strcmp(s1,s2)<0; } int main() { //freopen("a.txt","r",stdin); char c,s[210]; int i,j=0,cnt=0,flag; while((c=getchar())!=EOF) { if(isalpha(c)) s[j++]=tolower(c); else if(j) { s[j]='\0'; for(i=0,flag=0;i<cnt;i++) { if(strcmp(s,str[i])==0) {flag=1;break;} } if(!flag) strcpy(str[cnt++],s); j=0; } } for(i=0;i<cnt;i++) { //printf("%s\n",str[i]); strp[i]=str[i]; } sort(strp,strp+cnt,cmp); for(i=0;i<cnt;i++) { printf("%s\n",strp[i]); } return 0; }
UVA - 10815 Andy's First Dictionary
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。