[String+Map版]从poj 1002——487-3279的STL做法和若干陷阱来分析MAP
求重复的号码东西。第一反应就是MAP(他们有用hash做的),写起来也很顺(我指针弱渣)实际应用的时候却发现了一些陷阱,导致了若干次的wa.
原理很简单:打表,转化成数字,忽略横杠,添加到MAP里,根据MAP自动管理的特性(自动保持升序,自动开内存++等)输出重复的次数。
但陷阱也挺麻烦,可能和我略奇葩的思维有关
1、删除横杠。
下面的代码,看上去很对有木有??删除横杠啊~
错解1:
[cpp]
string::iterator it;
for(it=tar.begin();it!=tar.end();it++)
{
if((*it)=='-')
{
tar.erase(it);
}
}
但是如果用这句来删除横杠,会报非法内存,为什么呢?不信你写个123-4-5-6--7--试试。即防不住两个横杠,也防不住最后的横杠,删着删着就出缓冲区了。。
正解,用别的字符串res存不就行了。。
[cpp]
for(int p=0;p<tar.size();p++)
{
if(isdigit(tar[p]))
res+=tar[p];
}
2、两种存入方式。
错解:无脑用map["1234567"]++存。存这个会报TLE,原理是按重载的运算符[]进行更新的话,会把所有的已知参数都搜索一遍,非常麻烦。
正解:分情况讨论
[cpp]
map<string,int>::iterator apper=phonepack.find(conv);
if(apper==phonepack.end())
{
phonepack.insert(map<string,int>::value_type(conv,1));
}
else
{
phonepack[conv]++;
}
3、注意没输出的情况,这个纯读题问题。
综合以上情况,终于能AC了,虽然也有点卡时间 1700/2000 MS...
[cpp]
#include <string>
#include <map>
#include <algorithm>
#include <ctype.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
map<string,int> phonepack;
string phonecall(string tar)
{
string res;
for(int i=0;i<tar.size();i++)
{
if(tar[i]=='A' || tar[i]=='B' || tar[i]=='C')
tar.replace(i,1,"2");
else if(tar[i]=='D' || tar[i]=='E' || tar[i]=='F')
tar.replace(i,1,"3");
else if(tar[i]=='G' || tar[i]=='H' || tar[i]=='I')
tar.replace(i,1,"4");
else if(tar[i]=='J' || tar[i]=='K' || tar[i]=='L')
tar.replace(i,1,"5");
else if(tar[i]=='M' || tar[i]=='N' || tar[i]=='O')
tar.replace(i,1,"6");
else if(tar[i]=='P' || tar[i]=='R' || tar[i]=='S')
tar.replace(i,1,"7");
else if(tar[i]=='T' || tar[i]=='U' || tar[i]=='V')
tar.replace(i,1,"8");
else if(tar[i]=='W' || tar[i]=='X' || tar[i]=='Y')
tar.replace(i,1,"9");
}
/*string::iterator it;
for(it=tar.begin();it!=tar.end();it++) //不加这一句可能会导致系统读取非法内存,因为删除了标识符就没了,-有很多会出错
{
if((*it)=='-')
{
tar.erase(it);
cout<<tar<<endl;
}
}*/
for(int p=0;p<tar.size();p++)
{
if(isdigit(tar[p]))
res+=tar[p];
}
return res;
}
int main()
{
int testcase;
map<string,int>::iterator it2;
cin>>testcase;
for(int i=0;i<testcase;i++)
{
string region;
string conv;
cin>>region;
conv=phonecall(region);
map<string,int>::iterator apper=phonepack.find(conv);
if(apper==phonepack.end())
{
phonepack.insert(map<string,int>::value_type(conv,1));
}
else
{
phonepack[conv]++;
}
}
int pos=0;//初始化,又WA一次
for(it2=phonepack.begin();it2!=phonepack.end();it2++)
{
if((*it2).second>1) //输出格式比较麻烦
{
for(int i=0;i<=2;i++)
cout<<(*it2).first[i];