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
Source Code |
Problem: 1002 | |
User: beforkeke |
Memory: 14004K | |
Time: 3844MS |
Language: Java | |
Result: Accepted |
* Source Code
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();
}
}
}
解题思路:
①获取输入数据后,进行映射处理,然后保存在map里,KEY是处理后的数据,value是重复次数
②保存时如果这个KEY在map中不存在,则put(key,1)
如果存在,则将newValue=value+1后put(key,newValue)
③提取,将value非1的值都提取出来,并将key和value都toString后合并成一个字符串存入arrlist
④对arrlist排序
⑤处理字符串,并输入。
小结:
①对集合类理解很浅薄,随便用了map和arraylist,这里应该是可以优化的
②错误:将arraylist的泛型设置为Integer型,将得到的粗加工字符串转成整形存入了Arraylist,导致提交的时候runtime...而题目给的测试数据情况不全面,这种错误主要是比如将电话号码00011001从字符串转为int时,是11001,前面的000是舍去的。所以如果有runtime而不解的同学,可以考虑测试下00000开头的一些case。
③集中精力于解决问题,类的设计很是丑陋,方法分出来等于没分。。。待以后对集合类加深理解后,一并优化代码。
分享到:
相关推荐
pku acm 1002 487-3279代码 二叉查找数实现 解题报告请访问:http://blog.csdn.net/china8848
pku acm 2299 Ultra-QuickSort代码,合并排序求逆序数,解题报告请访问:http://blog.csdn.net/china8848
pku acm竞赛专用,含有多种算法的解题报告,程序员提高自身水平可以参考,会极大地提高编程功力-pku acm race-exclusive and contain a variety of algorithms to solve problems, programmers can improve their ...
pku acm 动态规划题1179解题报告
poj经典数据结构题目解题报告,包括经典的数据结构题目10多道,可以作为学习数据结构系统的资料,包括题目: Pku acm 3253 Fence Repair Pku acm 1861 NetWork Pku acm 2485 Highways Pku acm 1258 Agri...
ACM PKU解题报告,希望对热爱ACM的朋友有用吧~加油哦,为ACM而努力吧~~
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
很详细的解题报告,欢迎下载........
pku acm 3041 Asteroids代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
pku acm 1007 DNA Sorting代码 逆序数 排序 解题报告请访问:http://blog.csdn.net/china8848
pku acm 1466 Girls and Boys代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
pku acm 2771 Guardian of Decency 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
pku acm 1961 Period代码 kmp算法。解题报告:http://blog.csdn.net/china8848
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
pku acm 1316 Self Numbers 代码,解题报告请访问: http://blog.csdn.net/china8848
pku acm 1274 The Perfect Stall 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
ACM.PKU解题报告.part2
pku acm 2406 Power Strings代码 kmp算法。解题报告:http://blog.csdn.net/china8848