Nickname
4460 단어 name
ZSUQ Messenger is similar with Tencent QQ. Each user will make a nickname for itself. Different users can have identical nickname. Some common ones, such as “Tom”, “Marry”, “Kate”, are frequently used. In a recent survey, the ZSUQ Company was astonished to find that there are no more than 5000 distinct nicknames that are being used. Being a member of the ZSUQ Company, you are asked to make a report, telling the number of users for each nick name. A complete list of all users’ nicknames is provided to you. Please note that nicknames are case insensitive.InputThe first line of the file contains an integer indicating the number of test cases.In each test case, there is an integer N in the first line (0 < N < 100,000). The following N lines describe N users’ nicknames. Each name consists of no more than 100 characters. There is a bland line between two cases.OutputFor each case, give out a list of the distinct nickname, one per line, followed by a bland space and the number of users who has this nickname. The names are in alphabetic order. There is no bland space at the beginning or the end of each line. Nicknames should be presented in lowercase letter. There is a bland line after each case.
제목: 한 그룹의 개수가 N(<=100000)인 닉네임이 있는데 그 중에서 대량의 중복(총 닉네임이 5000개 미만)이 있어 각 닉네임의 개수를 구해야 한다.추가 정보: 닉네임은 대소문자를 가리지 않고 사전 오름차순으로 출력되며 닉네임의 길이는 100을 넘지 않습니다(L로 기재).
해석: 닉네임을 소문자로 변환한 후, 먼저 빨리 줄을 서고, (O (Lnlongn), 다시 한 번 중복된, (O (Ln) 을 스캔합니다.
하지만 간단하지만 복잡도가 높다.hash를 사용하면 문자열을 26진수로 삼아hash값 (O(L) 을 구하고, 선형 오픈 주소법으로 hash 충돌을 해결합니다.이렇게 하면 복잡도 복잡도는 O(Ln)이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int maxCount=6000; //hash
typedef struct {
char * name;
int count;
}Student;
// , qsort
int cmp(const void* s1,const void* s2){
Student *ss1=(Student *)s1;
Student *ss2=(Student *)s2;
return strcmp(ss1->name,ss2->name);
}
// hash
int hash(char* str){
int result=0;
for(char* p=str;*p!=0;p++){
result=result*26+(*p)-96;
}
return result%maxCount;
}
//
char *toLower(char *s){
char *p;
for (p=s; *p; p++){
if (*p >= 'A' && *p <= 'Z')
*p = *p - 'A' + 'a';
}
return s;
}
Student hashTable[maxCount];
int main(){
FILE *input=fopen("nickname.in","r");
FILE *output=fopen("nickname.out","w");
int n,nickNum; //nickNum
int testcase,index;
char str1[100],str2[100];
for( fscanf(input,"%d",&testcase);testcase>0;testcase--){
memset(hashTable,0,sizeof(hashTable));
fscanf(input,"%d",&n); //
for(int i=0;i<n;i++){ //n
fscanf(input,"%s",str1);
strcpy(str2,toLower(str1));
index=hash(str2);
//
while(hashTable[index].name!=NULL&&strcmp(hashTable[index].name,str2)!=0){ //hash
index++;
if(index>=maxCount)
index=0;
}
if(hashTable[index].name==NULL){ //
hashTable[index].name=new char[strlen(str2)+1];
strcpy( hashTable[index].name,str2);
hashTable[index].count=1;
}else{ //
hashTable[index].count++;
}
}
// ,
nickNum=0;
for(int i=0;i<maxCount;i++){
if(hashTable[i].count!=0){
hashTable[nickNum++]=hashTable[i];
}
}
qsort(hashTable,nickNum,sizeof(Student),cmp);
for(int i=0;i<nickNum;i++){
fprintf(output,"%s %d
",hashTable[i].name,hashTable[i].count);
}
fprintf(output,"
");
}
return 0;
}
입력:
33hello ohoh2shitshit9helloputabsabsputhellottehelloput
출력:
hello 1oh 2shit 2abs 2hello 3put 3tte 1
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SetupDiClassGuidsFromNameSetupDiClassGuidsFromName function retrieves the GUID(s) associated with the specified class name. This list is built ba...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.