Question

哪位大侠帮忙看看poj 1002 wrong answer！实在没办法了。搞一晚上了！

#include <stdio.h>
#include <stdlib.h>

struct node{
int pos;
node* next;
};

int ctoi(char c);
void printDeck();
int cmp(char* a,char* b);
void add(node* nn);
void add2(int j);
void sift();

node* pNode;
node* ht[254]={0};
char** deck;
int n=0;
int *count=NULL;
int* total=NULL;
int main ()
{
char c=0;
int j=0;
scanf ("%d%c",&n,&c);

count=(int *)malloc(sizeof(int) * n);
deck=(char**)malloc(sizeof(char*) * n);
total=(int*)malloc(sizeof(char) * n);

for(int i=0;i<n;i++){
count[i]=1;
deck[i]=(char*)malloc(sizeof(char) * 7);
}

for (int i=0;i<n;i++)
{
j=0;
total[i]=0;
while( ( c=getchar() ) != '\n')
{
if ((c>='0'&&c<='9') ||(c>='A'&& c<='Z'))
{
deck[i][j++]=ctoi(c);
total[i] += deck[i][j-1]*j;
}
}
add2(i);
}

sift();
printDeck();
return 0;

}

int ctoi(char c)
{
if(c>='0' && c<='9'){
return c-48;
}
c=c-65;
if(c<16){
return (int)c/3+2;
}
else
{
c--;
return (int)c/3+2;
}

}//end function ctoi

void printDeck()
{
int pos=0;
node* p=pNode;
while (p){
pos=p->pos;
for (int j=0;j<7;j++){
printf ("%d",deck[pos][j]);
if(j==2)
printf ("-");
}
printf (" %d\n",count[pos]);
p=p->next;
}
if (!pNode)
printf ("No duplicates.\n");

}

int cmp(char* a,char* b)
{
int i=0;
for (i=0;i<7&&a[i]==b[i];i++);
if (i==7)
return 0;
else
return a[i]-b[i];

}

void add(node* nn)
{
node* cur=NULL,*prior=NULL;
nn->next=NULL;
if(!pNode)
pNode=nn;
else{
cur=pNode;
while(cur&&cmp(deck[nn->pos],deck[cur->pos])>0 )
{
prior=cur;
cur=cur->next;
}
if (!prior){
nn->next=pNode;
pNode=nn;
}
else{
nn->next=cur;
prior->next=nn;
}
}
}

void add2(int j)
{
node *cur=NULL,*prior=NULL;
node *nn;
node *&p=ht[ total[j] ];

if(!p){
p=(node*)malloc( sizeof(node) );
p->next=NULL;
p->pos=j;
}
else{
cur=p;
while(cur&&cmp(deck[j],deck[cur->pos])>=0 )
{
prior=cur;
cur=cur->next;
}

if (!prior){
nn=(node*)malloc( sizeof(node) );
nn->pos=j;
nn->next=p;
p=nn;
}
else{
if( cmp( deck[j],deck[prior->pos])==0 ){
count[prior->pos]++;
}
else{
nn=(node*)malloc( sizeof(node) );
nn->pos=j;
nn->next=prior->next;
prior->next=nn;
}
}
}

}

void sift()
{
node* prior=NULL,*cur=NULL;

for (int i=0;i<253;i++)
{
cur=ht[i];
while (cur){
if(count[cur->pos]==1){
prior=cur;
cur=cur->next;
free(prior);
}else
{
prior=cur;
cur=cur->next;
add(prior);
}
}

}
}

小弟初来乍到，各位见笑了。
我的思路是：转换之后；顺次放进链式哈希表ht[]中；这样复杂度可能会小于n^2。
然后把哈希表里的节点，放进一个ascending链表里；
顺次打印；

最好能说说这道题目的 边界值问题或者别的什么问题！

希望能指出我的错误；

不用很具体；

Answer 1

代码过于冗长.....无法下手...贴出自己代码 参考用
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;

int compare(const void*elem1,const void*elem2)
{
return strcmp((char*)elem1,(char*)elem2);
}

int main()
{
bool gggg;
char map[]="22233344455566677778889999";//注意
char str[80];
char a[100001][9];
int n,m,i,j,len,ff;
int x=0,y;
cin>>n;
m=n;
while(m--)
{
y=0;
scanf("%s",str);
len=strlen(str);
//cout<<len<<endl;
for(i=0;i<len;i++)
{
if(str[i]=='-') continue;
if(str[i]>='A' && str[i]<='Z')
{
a[x][y]=map[str[i]-'A'];
y++;
continue;
}
a[x][y]=str[i];
y++;
}
a[x][y]='\0';
x++;

}

�

qsort(a,n,9,compare);

gggg=true;
i=0;
while(i<n)
{
j=i;
i++;
while(i<n && strcmp(a[i],a[j])==0)
i++;
if(i-j>1)
{
for(ff=0;ff<3;ff++)
cout<<a[i-1][ff]; cout<<"-";
for(ff=3;ff<7;ff++)
cout<<a[i-1][ff];
cout<<" "<<i-j<<endl;
//for(i=0;i<n;i++)
//printf("%s\n",a[i]);
gggg=false;
}
}
if(gggg==true)
cout<<"No duplicates."<<endl;

return 0;
}

Answer 2

#include<stdio.h>
#include<string.h>
#include<algorithm>
struct node
{char s[101];
}p[100000];
bool cmp(node a,node b)
{return strcmp(a.s,b.s)<0;
}
int cmp(const void *a,const void *b)
{return strcmp(((node*)a)->s,((node*)b)->s);}
char c2i(char c)
{if(c>47&&c<58)
return c;
if(c=='A'||c=='B'||c=='C')
return 50;
if(c=='D'||c=='E'||c=='F')
return 51;
if(c=='G'||c=='H'||c=='I')
return 52;
if(c=='J'||c=='K'||c=='L')
return 53;
if(c=='M'||c=='N'||c=='O')
return 54;
if(c=='P'||c=='R'||c=='S')
return 55;
if(c=='T'||c=='U'||c=='V')
return 56;
if(c=='W'||c=='X'||c=='Y')
return 57;
return 0;
}
void fun(char s[])
{int len=strlen(s),i,c=0;
char t[101];
for(i=0;i<len;i++)
{if(c2i(s[i]))
t[c++]=c2i(s[i]);
if(c==3)
t[c++]='-';
}
t[c]=0;
strcpy(s,t);
}
main()
{int n,i,c=0,f=1;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s",p[i].s),fun(p[i].s);
std::qsort(p,n,sizeof(node),cmp);
for(i=0;i<n;i++)
if(!strcmp(p[i].s,p[i+1].s))
c++,f=0;
else if(c)
printf("%s %d\n",p[i].s,c+1),c=0;
if(f)
puts("No duplicates.");
}

Answer 3

简单