还是水题，不过也折腾了很久，下面是AC的解法，效率不高，问题在于我是对字符串进行操作，看到有人将电话号码转化为整形数据，这样排序处理会快很多，空间占用也小。末尾附上无数次WA的解法，试过了能找到的所有测试数据，都没有问题，如果谁能指出错误所在，感激不尽。
#include <iostream>
#include <string>
using namespace std;
int cmpare(const void *str1,const void *str2)
{
//注释掉的是我从msdn上找到的例子，不知道为什么总是出错，还是自己熟悉的用法好
//return
_stricmp( * ( char** ) str1, * ( char** ) str2 );
return
strcmp((char *)str1,(char
*)str2);
}
int main()
{
int
num;
bool
flag=false;
cin>>num;
string str;
//用hash实现字母到数字的转换，注意Q的位置是空的
char
cv[100000][8],hash[]={'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'};
int
pre=0,suf=0,i,count=1,ix;
for(int ix=0;ix<num;++ix)
{
str.empty();
cin>>str;
i=0;
for(int index=0;index<str.size();++index)
{
if(str[index]>='0'&&str[index]<='9')
cv[ix][i++]=str[index];
else if(str[index]>='A'&&str[index]<'Z')
cv[ix][i++]=hash[str[index]-'A'];
}
cv[ix][i]='/0';
}
qsort((void
*)cv,(size_t)num,sizeof(cv[0]),cmpare);
//cout<<"after:"<<endl;
//for(int
ix=0;ix<num;++ix)
//{
//cout<<cv[ix]<<endl;
//}
for(ix=1;ix<num;++ix)
{
if(strcmp(cv[ix],cv[ix-1])==0)
count++;
else
if(count>1)
{
flag=true;
pre=(cv[ix-1][0]-'0')*100+(cv[ix-1][1]-'0')*10+cv[ix-1][2]-'0';
suf=(cv[ix-1][3]-'0')*1000+(cv[ix-1][4]-'0')*100+(cv[ix-1][5]-'0')*10+cv[ix-1][6]-'0';
printf("%03d-%04d %d/n",pre,suf,count);
count=1;
}
}
if(count>1)//这个地方特别重要 对最后一组数进行处理
{
flag=true;
pre=(cv[ix-1][0]-'0')*100+(cv[ix-1][1]-'0')*10+cv[ix-1][2]-'0';
suf=(cv[ix-1][3]-'0')*1000+(cv[ix-1][4]-'0')*100+(cv[ix-1][5]-'0')*10+cv[ix-1][6]-'0';
printf("%03d-%04d %d/n",pre,suf,count);
count=1;
}
if(!flag)//注意没有输出的情况
cout<<"No duplicates."<<endl;
return
0;
}
这是WA的情况，一直不知道为什么，如果是因为使用了C++的类map、string的话，也应该是超时之类的错误啊。
#include <iostream>
#include <string>
#include <map>
using namespace std;
void makeChart(map<char,char> &);
void transfer(string &,map<char,char> &);
int main()
{
int
num;
cin>>num;
string orig;
map<char,char> chart;
makeChart(chart);
map<string,int>
phoneCount;
for(int ix=0;ix<num;++ix)
{
cin>>orig;
transfer(orig,chart);
phoneCount[orig]++;
}
bool
flag=false;
for(map<string,int>::iterator
iter=phoneCount.begin();iter!=phoneCount.end();++iter)
{
if(iter->second>1)
{
flag=true;
cout<<iter->first<<" "<<iter->second<<endl;
}
}
if(!flag)
cout<<"No duplicates."<<endl;
return
0;
}
void makeChart(map<char,char> &chart)
{
chart.insert(make_pair('A','2'));
chart.insert(make_pair('B','2'));
chart.insert(make_pair('C','2'));
chart.insert(make_pair('D','3'));
chart.insert(make_pair('E','3'));
chart.insert(make_pair('F','3'));
chart.insert(make_pair('G','4'));
chart.insert(make_pair('H','4'));
chart.insert(make_pair('I','4'));
chart.insert(make_pair('G','5'));
chart.insert(make_pair('K','5'));
chart.insert(make_pair('L','5'));
chart.insert(make_pair('M','6'));
chart.insert(make_pair('N','6'));
chart.insert(make_pair('O','6'));
chart.insert(make_pair('P','7'));
chart.insert(make_pair('R','7'));
chart.insert(make_pair('S','7'));
chart.insert(make_pair('T','8'));
chart.insert(make_pair('U','8'));
chart.insert(make_pair('V','8'));
chart.insert(make_pair('W','9'));
chart.insert(make_pair('X','9'));
chart.insert(make_pair('Y','9'));
}
void transfer(string &str,map<char,char>
&chart)
{
string tempstr;
for(int ix=0;ix<str.size();++ix)
{
if(str[ix]=='-')
continue;
else
if(str[ix]>='A'&&str[ix]<='Z')
tempstr.push_back(chart[str[ix]]);
else
tempstr.push_back(str[ix]);
}
tempstr.insert(3,"-");
str=tempstr;
}