ACM的一道题……POJ-1002
Description
企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Gino's订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。
电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。 TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。
如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）
你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。
Input
输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。
Output
对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：
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
代码：
- Java code
import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Scanner;public class Main_1002 { public static char map(char Char) { switch(Char) { case 'A': case 'B': case 'C': return '2'; case 'D': case 'E': case 'F': return '3'; case 'G': case 'H': case 'I': return '4'; case 'J': case 'K': case 'L': return '5'; case 'M': case 'N': case 'O': return '6'; case 'P': case 'R': case 'S': return '7'; case 'T': case 'U': case 'V': return '8'; case 'W': case 'X': case 'Y': return '9'; case '-': return ' '; default : return Char; } } public static String convert(String num) { char[] NUM = num.toCharArray(); int length = NUM.length; List<Character> numbers = new ArrayList<Character>(); char digit; for(int i = 0; i < length; i++) { digit = map(NUM[i]); if(digit != ' ') numbers.add(digit); } num = ""; for(int i = 0; i < numbers.size(); i++) { num += numbers.get(i); if(i == 2) num += "-"; } return num; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList<String> list = new ArrayList<String>(); Map<String, Integer> map = new HashMap<String, Integer>(); String num = null; int freq; int n = sc.nextInt(); for(int i = 0; i < n ; i++) { num = convert(sc.next()); if(!list.contains(num)) list.add(num); freq = map.get(num) == null ? 0 : map.get(num); map.put(num, freq == 0 ? 1 : ++freq); } Collections.sort(list); boolean flag = false; for(int i = 0; i < list.size(); i++) { num = list.get(i); freq = map.get(num); if(freq != 1) { if(flag == false) System.out.print(num + " " + freq); else System.out.print("\n" + num + " " + freq); flag = true; } } if(flag == false) System.out.print("No duplicates."); }}
老是Runtime Error。不知道哪里可能会出问题？
[解决办法]
- Java code
import java.util.*;import java.io.*;import java.util.regex.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String line=""; int total=Integer.parseInt(br.readLine()); StringBuilder builder=null; HashMap<String,Integer> map=new HashMap(); for(int t=0;t<total;t++){ line=br.readLine(); builder=new StringBuilder(); Pattern p=Pattern.compile("\\w+"); Matcher m=p.matcher(line); while(m.find()) builder.append(m.group()); for(int i=0;i<builder.length();i++){ if(builder.charAt(i)>='A'&&builder.charAt(i)<='Z'){ int num=builder.charAt(i)-'A'; if(num>16) builder.replace(i,i+1,((num-1)/3+2)+""); else builder.replace(i,i+1,(num/3+2)+""); } } builder.insert(3,'-'); String s=builder.toString(); if(map.containsKey(s)){ map.put(s,map.get(s)+1); } else map.put(s,1); } Iterator<String> iter=map.keySet().iterator(); ArrayList<String> list=new ArrayList(); while(iter.hasNext()){ list.add(iter.next()); } Collections.sort(list); boolean flag=false; String key=null; for(int i=0;i<list.size();i++){ key=list.get(i); if(map.get(key)>1){ flag=true; System.out.println(key+" "+map.get(key)); } } if(!flag) System.out.println("No duplicates."); }}
[解决办法]
给你个C++代码- C/C++ code
#include <iostream>#include <stdlib.h>#include <string>using namespace std;int compare( const void *a,const void *b){ return strcmp( (char *)a,(char *)b );}char str[100000][8];char into[27]="22233344455566677778889999";int main(){#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endif int n,i,j,k; char a[50]; scanf("%d\n",&n); for (i=0;i<n;i++) { scanf("%s\n",&a); for ( k=j=0;j<strlen(a);j++,k++ ) { if ( a[j]>='0' && a[j]<='9' ) str[i][k]=a[j]; else if ( a[j]>='A' && a[j]<='Z' ) str[i][k]=into[ a[j]-'A' ]; else k--; } } qsort(str,n,8,compare); int t=0; for (i=0;i<n-1;) { int count=1; for (j=i+1;j<n;j++) { if ( !strcmp(str[i],str[j]) ) count++; else break; } if ( count>=2 ) { printf("%c%c%c-%s %d\n",str[i][0],str[i][1],str[i][2],str[i]+3,count); t++; } i=j; } if( !t ) printf("No duplicates.\n"); return 0;}