PKU ACM 1002- 487-3279-解题报告

[color=darkred]487-3279

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 105781 Accepted: 17808

Description
Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their ``three tens'' number 3-10-10-10.

The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:

A, B, and C map to 2
D, E, and F map to 3
G, H, and I map to 4
J, K, and L map to 5
M, N, and O map to 6
P, R, and S map to 7
T, U, and V map to 8
W, X, and Y map to 9

There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.

Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.

Input
The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.

Output
Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:

No duplicates.

Sample Input

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

Sample Output

310-1010 2
487-3279 4
888-4567 3

Source
East Central North America 1999[/color]

[table]
|Source Code|
|Problem: 1002|
|User: beforkeke|
|Memory: 14004K|
|Time: 3844MS|
|Language: Java|
|Result: Accepted|
[/table]

[size=medium][color=red]* Source Code[/color][/size]

import java.io.*;
import java.util.*;
class Main {
	//test
	public static HashMap<String,Integer> hashmap = new HashMap<String,Integer>();
	public static Scanner sin;
	public static void doConvertAndSave(int count){
		for (int i = 0; i<count; i++) {
				String s =sin.next();		
				StringBuffer sb = new StringBuffer("");
				for (int j = 0; j < s.length(); j++) {
					switch(s.charAt(j)){
						case '-':
							break;
						case 'A':case 'B':case 'C':
							sb.append(2);
							break;
						case 'D':case 'E':case 'F':
							sb.append(3);
							break;
						case 'G':case 'H':case 'I':
							sb.append(4);
							break;
						case 'J':case 'K':case 'L':
							sb.append(5);
							break;	
						case 'M':case 'N':case 'O':
							sb.append(6);
							break;
						case 'P':case 'R':case 'S':
							sb.append(7);
							break;	
						case 'T':case 'U':case 'V':
							sb.append(8);
							break;	
						case 'W':case 'X':case 'Y':
							sb.append(9);
							break;
						case 'Q':case 'Z':
							continue;	
						default:
							sb.append(s.charAt(j));	
					}
				}
					String tempStringForSave = sb.toString();
				if(!hashmap.containsKey(tempStringForSave)){
					hashmap.put(tempStringForSave,1);
				}
				else{
					int newVal = hashmap.get(tempStringForSave)+1;
					hashmap.put(tempStringForSave,newVal);
				}	
		}
	}
	public static void main(String[] args){
		sin=new Scanner(System.in);
		try{
			int count=sin.nextInt();
			doConvertAndSave(count);
			ArrayList<String> ar = new ArrayList<String>();
			Iterator it = hashmap.keySet().iterator();
			int resultCount = 0;                                                                                               
			while(it.hasNext()){
				String resultString = (String)it.next();	
					//System.out.println("KKK"+resultString);		
				int resultTimes =hashmap.get(resultString);
				if( resultTimes != 1){
					resultString += resultTimes; 
					ar.add(resultString);
				}
			}	
			if(ar.size() == 0)
			{
				System.out.println("No duplicates.");
			}
			Collections.sort(ar);
			Iterator it2 = ar.iterator();
			while (it2.hasNext()) {
				String tempStringForSave2 = it2.next().toString();
				tempStringForSave2	= tempStringForSave2.substring(0,3)+
													"-"+tempStringForSave2.substring(3,7)+
													" " +tempStringForSave2.substring(7) ;
				System.out.println(tempStringForSave2);
			}
		}
		catch(Exception e){
			e.printStackTrace();
		}

	}
}

[color=blue]解题思路：
①获取输入数据后，进行映射处理，然后保存在map里，KEY是处理后的数据，value是重复次数
②保存时如果这个KEY在map中不存在，则put(key,1)
如果存在，则将newValue=value+1后put(key,newValue)
③提取，将value非1的值都提取出来，并将key和value都toString后合并成一个字符串存入arrlist
④对arrlist排序
⑤处理字符串，并输入。[/color]


[color=indigo]小结：
①对集合类理解很浅薄，随便用了map和arraylist，这里应该是可以优化的
②错误：将arraylist的泛型设置为Integer型，将得到的粗加工字符串转成整形存入了Arraylist，导致提交的时候runtime...而题目给的测试数据情况不全面，这种错误主要是比如将电话号码[phone]从字符串转为int时，是11001，前面的000是舍去的。所以如果有runtime而不解的同学，可以考虑测试下00000开头的一些case。
③集中精力于解决问题，类的设计很是丑陋，方法分出来等于没分。。。待以后对集合类加深理解后，一并优化代码。[/color]