POJ1002 方便记忆的电话号码

一时失言乱红尘 2021-09-23 02:24 254阅读 0赞

**问题描述**  
总时间限制: 2000ms 内存限制: 65536kB  
**描述**  
英文字母（除Q和Z外）和电话号码存在着对应关系，如下所示：

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

标准的电话号码格式是xxx-xxxx，其中x表示0-9中的一个数字。有时为了方便记忆电话号码，我们会将电话号码的数字转变为英文字母，如把263-7422记成America。有时，我们还加上“-”作为分隔符，如把449-6753记成Hi-World。当然，我们未必要将所有的数字都转变为字母，比如474-6635可以记成iPhone-5。

总之，一个方便记忆的电话号码由数字和除Q、Z外的英文字母组成，并且可以在任意位置插入任意多的“-”符号。

现在 ，我们有一个列表，记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码，你的任务就是找出它们。

**输入**  
第一行是一个正整数n（n <= 100000），表示列表中的电话号码数。  
其后n行，每行是一个方便记忆的电话号码，它由数字和除Q、Z外的英文字母、“-”符号组成，其中数字和字母的总数一定为7，字符串总长度不超过200。

**输出**  
输出包括若干行，每行包括一个标准电话号码（xxx-xxxx）以及它重复出现的次数k（k >= 2），中间用空格分隔。输出的标准电话号码需按照升序排序。  
如果没有重复出现的标准电话号码，则输出一行“No duplicates.”。

**样例输入**  
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

**样例输出**  
310-1010 2  
487-3279 4  
888-4567 3

import java.lang.Character;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.Scanner;
    import java.util.TreeMap;
    
    public class Main { 
        private static Map<Character, Character> map;
        private static Map<String, Integer> mapResult;
    
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            initMap();
            mapResult = new HashMap<String, Integer>();
            Scanner scanner = new Scanner(System.in);
            int N = Integer.valueOf(scanner.nextLine());// 共N行数据
            String temp;
            String result;
            int value = 0;
            for (int i = 0; i < N; i++) {
                temp = scanner.nextLine();// 读取一行数据
                // 解析该数字
                result = f(temp);
                if (mapResult.containsKey(result)) {
                    value = mapResult.get(result) + 1;
                    mapResult.put(result, value);
                } else {
                    mapResult.put(result, 1);
                }
            }
            //long l =System.currentTimeMillis();
            print(mapResult);
            //System.out.println(System.currentTimeMillis()-l);
        }
    
        // 解析数字字母字符串为数字字符串
        private static String f(String temp) {
            // TODO Auto-generated method stub
            String r = "";
            char[] ch = temp.toCharArray();
            for (int i = 0; i < ch.length; i++) {
                if (ch[i] == '-')
                    continue;
                if (ch[i] >= '0' && ch[i] <= '9') {
                    r += ch[i];
                    continue;
                }
                r += map.get(Character.valueOf(ch[i]));
            }
            return r;
        }
    
        // 数字与字母之间的映射关系
        private static void initMap() {
            // TODO Auto-generated method stub
            map = new HashMap<Character, Character>();
            map.put('A', '2');
            map.put('B', '2');
            map.put('C', '2');
            map.put('D', '3');
            map.put('E', '3');
            map.put('F', '3');
            map.put('G', '4');
            map.put('H', '4');
            map.put('I', '4');
            map.put('J', '5');
            map.put('K', '5');
            map.put('L', '5');
            map.put('M', '6');
            map.put('N', '6');
            map.put('O', '6');
            map.put('P', '7');
            map.put('R', '7');
            map.put('S', '7');
            map.put('T', '8');
            map.put('U', '8');
            map.put('V', '8');
            map.put('W', '9');
            map.put('X', '9');
            map.put('Y', '9');
        }
    
        private static void print(Map<String, Integer> mapResult2) {
            Map<String, Integer> r = new TreeMap<String, Integer>();
    
            String temp="";
            for (Entry<String, Integer> mm : mapResult2.entrySet()){
                if(mm.getValue()>1){
                    temp=mm.getKey().substring(0, 3)+"-"+mm.getKey().substring(3);      
                    r.put(temp, mm.getValue());
                }
            }
    
            if(r.size()>0){
                for (Entry<String, Integer> mm : r.entrySet()){
                    if(mm.getValue()>1){
                        System.out.println(mm.getKey()+" "+mm.getValue());
                    }
                }
            }else{
                System.out.println("No duplicates.");
            }
        }
    }

小结：  
Java中Treemap具有排序功能，但是读取插入速度比HashMap慢，因为Hashmap是基于散列表，而TreeMap是基于红黑树实现，始终处于平衡状态。HashMap适合在Map中定位、删除和插入元素，TreeMap适用于按照自然顺序或者自定义顺序遍历列。  
在此题中，由于输出需要排序，使用了TreeMap，但是增加了时间成本，本段代码运行数据量大的时候耗时很多，请大家指教。