POJ1002487-3279(map)

2013-11-03 来源: 枫、 发布在  http://www.cnblogs.com/luyingfeng/p/3404552.html

http://poj.org/problem?id=1002

题意:是说很多公司用了容易记住的电话号码,例如有英文字母的或者是用了很多连字符或没有连字符的。每个电话号码都有标准模式,而为了统计有没有重复的电话号码,就要统计有多少的电话号码是重复的,只要是有重复的就输出他的标准模式,如果所有的字符串都没有重复的,就输出No duplicates.

思路:这个题就用了普通的枚举,用的是cin输入的,结果是超时了,后来改成scanf就A了。这个题还可以用map去做,以及在排序的时候转换成整型会省更多的时间,后两种方法,第一种方法用时1454ms,第三种方法用时574ms,至于map我还没写,夜实在是深了,我先睡了,明天去做一下 。

普通方法

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<algorithm>

using namespace std ;

";
] ,sh[][];
int n ,j;

int cmp(const void *b,const void *c)
{
    return strcmp((char *)b,(char *)c) ;
}
void cuizhehundan()
{
    int len = strlen(ch) ;
     ;
     ; i < len ; i++)
    {
        ')
            sh[j][flag++] = ch[i] ;
        if(ch[i] == '-'||ch[i] == 'Q'||ch[i] == 'Z')
            continue ;
        if(ch[i] >= 'A'&&ch[i] < 'Z')
            sh[j][flag++] = a[ch[i]-'A'];
    }
    sh[j][flag] = '\0' ;
    //cout<<sh[j]<<endl;
}

int main()
{
    int n ;
    cin>>n ;
     ; j < n ; j++)
    {
        scanf("%s",ch) ;
        cuizhehundan();
    }
    qsort(sh,n,]),cmp) ;
     ;
     ; i < n- ; i++)
    {
        ;
       // int x = i ;
         &&strcmp(sh[i],sh[i+]) == )
        {
                num++ ;
                i++ ;
        }
        )
        {
             ; h <  ; h++)
                printf("%c",sh[i][h]);
            cout<<'-';
             ; h < ; h++)
                printf("%c",sh[i][h]);
               // cout<<" ";
                printf(" %d\n",num) ;
            //cout<<num<<endl;
            mark =  ;
        }
        num = ;
    }
    if(!mark)
    printf("No duplicates.\n");
     ;
}

转化整型

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<algorithm>

using namespace std ;

";
] ;
];
int n ,j;

void cuizhehundan()
{
    int len = strlen(ch) ;
     ;
     ; i < len ; i++)
    {
        ')
            sh[flag++] = ch[i] ;
        if(ch[i] == '-'||ch[i] == 'Q'||ch[i] == 'Z')
            continue ;
        if(ch[i] >= 'A'&&ch[i] < 'Z')
            sh[flag++] = a[ch[i]-'A'];
    }
    sh[flag] = '\0' ;
//    for(int i = 0 ; i < len ; i++)
//    cout<<sh[i];
//    cout<<endl;
}

int main()
{
    int n ;
    cin>>n ;
    ] ;
     ; j < n ; j++)
    {
        scanf("%s",ch) ;
        cuizhehundan();
        shh[j] = atoi(sh) ;
    }
    sort(shh,shh+n) ;
    //qsort(sh,n,sizeof(sh[0]),cmp) ;
     ;
     ; i < n- ; i++)
    {
        ;
       // int x = i ;
         &&shh[i]==shh[i+])
        {
                num++ ;
                i++ ;
        }
        )
        {
            printf(,shh[i]%,num) ;
            mark =  ;
        }
        num = ;
    }
    if(!mark)
    printf("No duplicates.\n");
     ;
}

说好的map做法,昨晚因为不舒服很早就睡了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<string>
#define maxn 1000
using namespace std;
char s1[maxn],s2[maxn];
char s3[]="2223334445556667Q77888999Z";
map<string, int>q;
void change(char s[])
{
    int k=strlen(s);
    ;
    ; i<k; i++)
    {
        if(s[i]!='Q'&&s[i]!='Z'&&s[i]!='-')
        {
            char c=s[i];
            if(s[i]>='A'&&s[i]<'Z')
            {
                c=s3[c-'A'];
            }
            )
                s2[j++]='-';
            s2[j++]=c;
        }
    }
    s2[j]='\0';
    //printf("%s\n",s2);
    if(q.find(s2)==q.end())
        q[s2]=;
    else
        q[s2]++;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s1);
        change(s1);
    }
    map<string,int>::iterator it=q.begin();
    bool flag=false;
    while(it!=q.end())
    {
        )
        {
            flag=true;
            cout<<it->first<<" "<<it->second<<endl;
        }
        it++;
    }
    if(!flag) printf("No duplicates.\n");
    ;
}

相关文章