POJ1002解题报告

我不是女神ヾ 2022-08-10 14:55 237阅读 0赞

原题[点击打开链接][Link 1]，网上很多人说是中文的，但是到我做的时候是英文的。题目大概意思就是讲字母可以代换数字，ABC代换2 DEF代换3 依次类推。

思路其实很简单，将输入的字串从 0到str.size()扫描 将字母转换为数字 ，遇到‘-’就跳过，最后将所有的数据存入整型数组中，最后对数组进行升序排序，对升序数组扫描，遇到有两个及以上相同的就输出结果（按照xxx-xxxx）的格式。

题目不难，但是提交了很多遍才AC，后来找其原因总结如下：

1.数组开的太小——出现runtime error。

2.排序算法不够省时，之前为了省事用冒泡这种原始的排序算法结果超时，建议用快排。

3.注意输出"No duplicates."，这个细节一定要注意，这也是我提交N遍的另一个小细节。

4.由于电话号码一定是7位，对于0000001,0000222，这样的数据（转化成整型小于1000000），输出的时候要特别注意格式。

代码如下：

/*
    Arthur:	Near_zh
    Date:	2014/07/31
    Note:	poj-1002
    */
    #include <iostream>
    #include <string>
    using namespace std;
    int cmp(const void* a,const void* b)
    {
    	return *(int*)a-*(int*)b;
    }
    int main()
    {
    	int N;
    	bool flag=false;
    	string str;
    	//int num[1000][1000];
    	int num[100000];
    	int temp;
    	cin>>N;
    	int i;
    	int j;
    	for( i=0;i<N;i++)
    	{
    		temp=0;
    		cin>>str;
    		for(j=0;j<str.size();j++)
    		{
    			if(str[j]<='9'&&str[j]>='0')
    			{
    				temp+=str[j]-'0';
    			}
    			else
    			{
    				switch (str[j])
    				{
    					case 'A':case 'B':case 'C':
    						temp+=2;
    						break;
    					case 'D':case 'E':case 'F':
    						temp+=3;
    						break;
    					case 'G':case 'H':case 'I':
    						temp+=4;
    						break;
    					case 'J':case 'K':case 'L':
    						temp+=5;
    						break;
    					case 'M':case 'N':case 'O':
    						temp+=6;
    						break;
    					case 'P':case 'R':case 'S':
    						temp+=7;
    						break;
    					case 'T':case 'U':case 'V':
    						temp+=8;
    						break;
    					case 'W':case 'X':case 'Y':
    						temp+=9;
    						break;
    					default:
    						continue;
    				}
    			}
    			temp*=10;
    		}
    		temp=temp/10;
    		num[i]=temp;
    	}
    	qsort(num,N,sizeof(num[0]),cmp);
    	int count;
    	for(i=0;i<N;i++)
    	{
    		count=1;
    		for(j=i;j<N;j++)
    		{
    			if(num[j]==num[j+1])
    			{
    				count++;
    			}
    			else
    				break;
    		}
    		char x;
    		int y=0;
    		string out;
    		if(count>=2)
    		{
    			flag=true;
    			out="";
    			int j=7;
    			while(j--)
    			{
    				x=num[i]%10+'0';
    				num[i]/=10;
    				out+=x;
    				y++;
    				if(y==4)
    				{
    					out+='-';
    				}
    			}
    			for(i=out.size()-1;i>=0;i--)
    				cout<<out[i];
    			cout<<" "<<count<<endl;
    		}
    		i=j;
    	}	
    	if(flag==false)
    		cout<<"No duplicates."<<endl;  
    	return 0;
    }

[Link 1]: http://poj.org/problem?id=1002