第一種方法。。較為繁瑣，用字典序寫的，用空間來換時間
[cpp]
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct trietree* Ptree;
struct trietree
{
bool arrive;
int treenum;
Ptree next[10];
} node[1000000];
int size;
bool findsolve;
void newtree(int no)
{
int i;
node[no].arrive=false;
node[no].treenum=0;
for(i=0; i<=9; i++)
{
node[no].next[i]=NULL;
}
}
int dispose(char *p)
{
int num=0;
char *q=p;
while(*++p!='\0');
p--;
while(p>=q)
{
if(*p=='-')
{
p--;
continue;
}
num*=10;
if(*p>='A'&&*p<='Y')
num+=(*p-'A'-(*p>'Q'))/3+2;
else if(*p>='0'&&*p<='9')
num+=*p-'0';
p--;
}
return num;
}
void addnum(int num)
{
Ptree p=&node[1];
int i,k;
for(i=0; i<=6; i++)
{
k=num%10;
num/=10;
if(!p->next[k])
{
newtree(++size);
p->next[k]=&node[size];
}
p=p->next[k];
}
p->arrive=true;
p->treenum++;
return ;
}
void dfs(char phone[9],int m,Ptree p)
{
if(true==p->arrive)
{
if(p->treenum>1)
{
for(int i=1; i<=7; i++)
{
if(i==4)
printf("-");
printf("%c",phone[i]);
}
printf(" %d\n",p->treenum);
findsolve=true;
}
return ;
}
for(int i=0; i<=9; i++)
{
if(p->next[i])
{
phone[m+1]=i+'0';
dfs(phone,m+1,p->next[i]);
}
}
return ;
}
int main()
{
int n,i,j;
int number;
char phone[9];
char ch[80];
scanf("%d",&n);
findsolve=false;
size=1;
newtree(1);
for(i=1; i<=n; i++)
{
scanf("%s",ch);
number=dispose(ch);
addnum(number);
}
dfs(phone,0,&node[1]);
if(!findsolve)
printf("No duplicates.\n");
return 0;
}
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct trietree* Ptree;
struct trietree
{
bool arrive;
int treenum;
Ptree next[10];
} node[1000000];
int size;
bool findsolve;
void newtree(int no)
{
int i;
node[no].arrive=false;
node[no].treenum=0;
for(i=0; i<=9; i++)
{
node[no].next[i]=NULL;
}
}
int dispose(char *p)
{
int num=0;
char *q=p;
while(*++p!='\0');
p--;
while(p>=q)
{
if(*p=='-')
{
p--;
continue;
}
num*=10;
if(*p>='A'&&*p<='Y')
num+=(*p-'A'-(*p>'Q'))/3+2;
else if(*p>='0'&&*p<='9')
num+=*p-'0';
p--;
}
return num;
}
void addnum(int num)
{
Ptree p=&node[1];
int i,k;
for(i=0; i<=6; i++)
{
k=num%10;
num/=10;
if(!p->next[k])
{
newtree(++size);
p->next[k]=&node[size];
}
p=p->next[k];
}
p->arrive=true;
p->treenum++;
return ;
}
void dfs(char phone[9],int m,Ptree p)
{
if(true==p->arrive)
{
if(p->treenum>1)
{
for(int i=1; i<=7; i++)
{
if(i==4)
printf("-");
printf("%c",phone[i]);
}
printf(" %d\n",p->treenum);
findsolve=true;
}
return ;
}
for(int i=0; i<=9; i++)
{
if(p->next[i])
{
phone[m+1]=i+'0';
dfs(phone,m+1,p->next[i]);
}
}
return ;
}
int main()
{
int n,i,j;
int number;
char phone[9];
char ch[80];
scanf("%d",&n);
findsolve=false;
size=1;
newtree(1);
for(i=1; i<=n; i++)
{
scanf("%s",ch);
number=dispose(ch);
addnum(number);
}
dfs(phone,0,&node[1]);
if(!findsolve)
printf("No duplicates.\n");
return 0;
}
第二種方法，參考別人的代碼~~，map容器實現。。簡單一點
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
using namespace std;
int num[] =
{
2, 2, 2,
3, 3, 3,
4, 4, 4,
5, 5, 5,
6, 6, 6,
7, 0, 7, 7,
8, 8, 8,
9, 9, 9
};
map<int, int> s;
char buf[128];
int main()
{
int t;
scanf("%d", &t);
bool flag = false;
for(int i = 0; i < t; i++)
{
scanf("%s", &buf);
int c = 0;
for(int j = 0; buf[j]; j++)
{
if(isdigit(buf[j]))
c = c * 10 + buf[j] - '0';
else if(isalpha(buf[j]))
c = c * 10 + num[ buf[j] - 'A' ];
}
s[c]++;
}
for(map<int, int>::iterator it = s.begin(); it != s.end(); it++)
if(it->second > 1)
{
flag = true;
printf("%03d-%04d %d\n", it->first / 10000, it->first % 10000, it->second);
}
if(!flag)
puts("No duplicates.");
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
using namespace std;
int num[] =
{
2, 2, 2,
3, 3, 3,
4, 4, 4,
5, 5, 5,
6, 6, 6,
7, 0, 7, 7,
8, 8, 8,
9, 9, 9
};
map<int, int> s;
char buf[128];
int main()
{
int t;
scanf("%d", &t);
bool flag = false;
for(int i = 0; i < t; i++)
{
scanf("%s", &buf);
int c = 0;
for(int j = 0; buf[j]; j++)
{
if(isdigit(buf[j]))
c = c * 10 + buf[j] - '0';
else if(isalpha(buf[j]))
c = c * 10 + num[ buf[j] - 'A' ];
}
s[c]++;
}
for(map<int, int>::iterator it = s.begin(); it != s.end(); it++)
if(it->second > 1)
{
flag = true;
printf("%03d-%04d %d\n", it->first / 10000, it->first % 10000, it->second);
}
if(!flag)
puts("No duplicates.");
return 0;
}
