POJ 1002：487-3279

作者: 梦工厂 | 来源:发表于2015-09-22 17:35 被阅读272次

总时间限制: 1000ms 内存限制: 65536kB

描述

企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打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。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）。
你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。

输入

输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。

输出

对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行： 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

超时代码
思路：
1）处理输入的电话号码，获取相应的int值。310-GINO -> 3104466
2）检验电话号码的重复次数（耗时操作，接近0(n2)）
3）对电话号码排序，格式化输出

import java.util.*;
public class Main{
   public static Map<Character,Integer> map = new HashMap<Character,Integer>();
   @SuppressWarnings("resource")
   public static void main(String args []){
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       int datas[] = new int[n];
       //初始化字符与int值得匹配
       initKeyMap(map); 
       //电话号码初始化
       for(int i=0;i<n;i++){
           datas[i] = get_number(scanner.next().trim().replace("-", ""));
       }
       //检验电话号码的重复次数
       Map<Integer,Integer> maps = checkDuplicate(datas);
       //格式化输出
       print(datas , maps);
   }
   private static void initKeyMap(Map<Character,Integer> map){
       for(int i =0;i<=9;i++){
           map.put((char)(i+48), i);
       }
       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(int datas[],Map<Integer,Integer> maps){
       boolean flag = false;//是否有重复号码
       StringBuilder phone;//格式化输出结果
       quickSort(datas,0,datas.length-1);//字典顺序输出
       for(int i = 0;i<datas.length;i++){
           if(datas[i] != -1 && maps.get(datas[i]) != 1){
               phone = new StringBuilder(String.valueOf(datas[i]));
               while(phone.length()<7){
                   phone.insert(0, "0");
               }
               phone.insert(3, "-");
               System.out.println(phone.toString() + " " + maps.get(datas[i]));
               flag = true;
           }
       }
       if( !flag ){
           System.out.println("No duplicates.");
       }
   }
   //检验电话号码的重复次数
   private static Map<Integer,Integer> checkDuplicate(int datas[]){
       Map<Integer,Integer> maps = new HashMap<Integer,Integer>();
       int temp;
       for(int i = 0;i<datas.length;i++){
           if( datas[i] == -1){
               continue;
           }
           temp = 1;
           for(int j = i+1;j<datas.length;j++){
               if(datas[i] == datas[j]){
                   temp ++ ;
                   datas[j] = -1;
               }
           }
           maps.put(datas[i], temp);
       }
       return maps;
   }
   //获取字符串电话号码对应的int值
   private static int get_number(String temp){
       int length = temp.length();
       int data[] = new int[length];
       for(int i =0;i<length;i++){
           data[i] = map.get(temp.charAt(i));
       }
       int result = 0;
       for(int i =0 ; i<length ; i++){
           result = result + data[i] * (int)Math.pow(10, length - 1 -i);
       }
       return result;
   }
   public static void quickSort(int a[],int l,int r){
        if(l>=r)
          return;
        int i = l; int j = r; int key = a[l];//选择第一个数为key
        while(i<j){
            while(i<j && a[j]>=key)//从右向左找第一个小于key的值
                j--;
            if(i<j){
                a[i] = a[j];
                i++;
            }
            while(i<j && a[i]<key)//从左向右找第一个大于key的值
                i++;
            if(i<j){
                a[j] = a[i];
                j--;
            }
        }
        //i == j
        a[i] = key;
        quickSort(a, l, i-1);//递归调用
        quickSort(a, i+1, r);//递归调用
    }
}

AC代码

import java.util.*;
public class Main {
    public static char getNum(char c) {
        if (Character.isDigit(c)) {
            return c;
        }
        if (c == 'A' || c == 'B' || c == 'C') {
            return '2';
        }
        if (c == 'D' || c == 'E' || c == 'F') {
            return '3';
        }
        if (c == 'G' || c == 'H' || c == 'I') {
            return '4';
        }
        if (c == 'J' || c == 'K' || c == 'L') {
            return '5';
        }
        if (c == 'M' || c == 'N' || c == 'O') {
            return '6';
        }
        if (c == 'P' || c == 'R' || c == 'S') {
            return '7';
        }
        if (c == 'T' || c == 'U' || c == 'V') {
            return '8';
        }
        if (c == 'W' || c == 'X' || c == 'Y') {
            return '9';
        }
        return '#';
    }
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        Map<String, Integer> maps = new TreeMap<String, Integer>();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String phone = scanner.next().trim().replace("-", "");
            StringBuffer sb = new StringBuffer();
            // 电话号码处理
            for (int j = 0; j < phone.length(); j++) {
                char c = getNum(phone.charAt(j));
                if (Character.isDigit(c)) {
                    sb.append(c);
                }
            }
            // 检验电话号码的重复次数
            phone = sb.toString();
            if (maps.containsKey(phone)) {
                int count = maps.get(phone) + 1;
                maps.put(phone, count);
            } else {
                maps.put(phone, 1);
            }
        }
        // 格式化输出
        boolean flag = false;// 是否有重复号码
        for (String key : maps.keySet()) {
            if (maps.get(key) > 1) {
                System.out.println(key.substring(0, 3) + "-" + key.substring(3)
                        + " " + maps.get(key));
                flag = true;
            }
        }
        if (!flag) {
            System.out.println("No duplicates.");
        }
    }
}

总结反思
key-value的关系优先考虑map，熟悉map的使用；
优先使用系统函数和数据结构。例如Character.isDigit(c)判断数字字符，Map<String, Integer> maps = new TreeMap<String, Integer>();实现排序的键值关系。

2015-09-22

网友评论

本文标题：POJ 1002：487-3279

本文链接：https://www.haomeiwen.com/subject/yryicttx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

POJ 1002：487-3279

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读