当前位置:编程学习 > C/C++ >>

[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];      
  &nb
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,