电话号码分身

pre

无聊刷了几条牛客网上的编程题，遇上了这一条，问题不难，但是有一些trick，我觉得比较有意思，这里就记录下解题的过程
问题链接:https://www.nowcoder.com/practice/493d71a992f44554a500ed818056e1a6

问题如下

题目描述
继MIUI8推出手机分身功能之后，MIUI9计划推出一个电话号码分身的功能：首先将电话号码中的每个数字加上8取个位，然后使用对应的大写字母代替 （”ZERO”, “ONE”, “TWO”, “THREE”, “FOUR”, “FIVE”, “SIX”, “SEVEN”, “EIGHT”, “NINE”）， 然后随机打乱这些字母，所生成的字符串即为电话号码对应的分身。
输入描述:
第一行是一个整数T（1 ≤ T ≤ 100)表示测试样例数；接下来T行，每行给定一个分身后的电话号码的分身（长度在3到10000之间）。
输出描述:
输出T行，分别对应输入中每行字符串对应的分身前的最小电话号码（允许前导0）。
示例1
输入
复制
4
EIGHT
ZEROTWOONE
OHWETENRTEO
OHEWTIEGTHENRTEO
输出
复制
0
234
345
0345

解题思路-1

根据题目描述，我已经能知道存在一种算法能根据乱序之后的字符串推断出原来号码数字的算法，也就是映射之前的英文数字的字符串中的字符相对位置没有任何意义
另外应该存在唯一的数字组合，这样一个数字组合与乱序之后的字符串一一对应，所以这里就直接采用试错法来检索数字就OK了。
至于要求输出数字串对应的最小电话号码，这个本身就是一个排序的问题，没有任何难度。

按照思路-1得到的代码

import java.util.*;

public class Main {

    private static Map<Character,Integer> getCharCountMap(String input){
        HashMap<Character,Integer> charCountMap = new HashMap<>();
        for(char singleChar : input.toCharArray()){
            if (!charCountMap.containsKey(singleChar)) {
                charCountMap.put(singleChar,0);
            }
            charCountMap.put(singleChar,charCountMap.get(singleChar)+1);
        }
        return charCountMap;
    }

    private static List<Integer> getNumberList(Map<Character, Integer> charCountMap, Map<Integer, Map> numToCharMap){
        List<Integer> numberList = new ArrayList<>();

        int index = 0;
        int numToCheck  = 0;
        while(charCountMap.size() > 0){
            //检查是否越界
            if(numToCheck > 9){
                index -- ;
                if(index < 0){
                    break;
                }
            }
            //确认是否发生回退
            if(index < numberList.size()){
                int preNum = numberList.get(index);
                //把字符还回去
                Map<Character, Integer> charMap = numToCharMap.get(preNum);
                for(char c : charMap.keySet()){
                    if(!charCountMap.containsKey(c)){
                        charCountMap.put(c,0);
                    }
                    charCountMap.put(c,charCountMap.get(c)+ charMap.get(c));
                }

                numToCheck = preNum+1;
            }

            //检查是否符合
            Map<Character, Integer> charMap = numToCharMap.get(numToCheck);
            boolean meetRequirment = true;
            for(Character c : charMap.keySet()){
                if(charCountMap.containsKey(c)){
                    if(charCountMap.get(c) < charMap.get(c)){
                        meetRequirment = false;
                        break;
                    }
                }else{
                    meetRequirment = false;
                    break;
                }
            }

            if(meetRequirment){
                for(char c : charMap.keySet()){
                    int newCount = charCountMap.get(c) -  charMap.get(c);
                    if(newCount == 0){
                        charCountMap.remove(c);
                    }else{
                        charCountMap.put(c,newCount);
                    }

                }
                numberList.add(numToCheck);

                index ++;
                numToCheck = 0;
            }else{
                numToCheck += 1;
            }
        }
        return numberList;
    }

    public static void main(String[] args){
        Map<Integer,String> numToEnglishMap = new HashMap<>();
        numToEnglishMap.put(0,"EIGHT");
        numToEnglishMap.put(1,"NINE");
        numToEnglishMap.put(2,"ZERO");
        numToEnglishMap.put(3,"ONE");
        numToEnglishMap.put(4,"TWO");
        numToEnglishMap.put(5,"THREE");
        numToEnglishMap.put(6,"FOUR");
        numToEnglishMap.put(7,"FIVE");
        numToEnglishMap.put(8,"SIX");
        numToEnglishMap.put(9,"SEVEN");

        Map<Integer,Map> numToCharMap = new HashMap<>();
        for(int num : numToEnglishMap.keySet()){
            String englishNum = numToEnglishMap.get(num);
            Map<Character,Integer> charCountMap = getCharCountMap(englishNum);
            numToCharMap.put(num,charCountMap);
        }

        Scanner in = new Scanner(System.in);
        int groups = in.nextInt();
        while(groups-- >0){
            String fenshen = in.next();
            Map<Character,Integer> charCountMap = getCharCountMap(fenshen);
            List<Integer> numMap = getNumberList(charCountMap,numToCharMap);
            Collections.sort(numMap);

            for(int i : numMap){
                System.out.print(i);
            }
            System.out.println();
        }
    }
}

运行结果

直接将代码放在网上测试，最后系统提示运行超时，这个也是理所应当的，毕竟试错法是最low的方法，中间存在着很多无效的计算。

修正之后解题思路-2

这里进一步观察数字和字符之间的映射关系，建立映射组,最后统计结果如下

E [0, 1, 2, 3, 5, 7, 9]
F [6, 7]
G [0]
H [0, 5]
I [0, 1, 7, 8]
N [1, 3, 9]
O [2, 3, 4, 6]
R [2, 5, 6]
S [8, 9]
T [0, 4, 5]
U [6]
V [7, 9]
W [4]
X [8]
Z [2]

这里可以知道，所有的偶数数字都存在唯一的字符与之对应，所有如果目标字符串中存在特定的字符，我们可以直接判断出来对应的偶数数字及其个数。

然后去掉偶数字符的统计，我们继续观察奇数数字与字符之间的映射关系。

R [5]
S [9]
T [5]
E [1, 3, 5, 7, 9]
F [7]
V [7, 9]
H [5]
I [1, 7]
N [1, 3, 9]
O [3]

我们可以发现，除了1之外其他的奇数数字都有唯一的字符与之对应，把所有的数字判断完成之后，剩下的字符就属于1了。

观察部分到这边为止，我们可以得到另外一种更加效率的解题方式，首先根据特定字符判断对应偶数数字是否存在，在根据一些字符判断除1之外的奇数数字是否存在，最后判断1是否存在。

解题思路2对应的代码

import java.util.*;

public class Main {

    private static Map<Character,Integer> getCharCountMap(String input){
        HashMap<Character,Integer> charCountMap = new HashMap<>();
        for(char singleChar : input.toCharArray()){
            if (!charCountMap.containsKey(singleChar)) {
                charCountMap.put(singleChar,0);
            }
            charCountMap.put(singleChar,charCountMap.get(singleChar)+1);
        }
        return charCountMap;
    }
    private static List<Integer> getNumberList(Map<Character, Integer> charCountMap, Map<Integer, Map> numToCharMap,Map<Character,Integer> charToSpecificNumMap){
        List<Integer> numberList = new ArrayList<>();

        for (Character outc : charToSpecificNumMap.keySet()){
            if(!charCountMap.containsKey(outc)){
                continue;
            }
            int numCount = charCountMap.get(outc);
            int num = charToSpecificNumMap.get(outc);
            Map<Character,Integer> charMap = numToCharMap.get(num);

            numCount /= charMap.get(outc);

            for(char inc : charMap.keySet()){
                int newCount = charCountMap.get(inc) -  charMap.get(inc)*numCount;
                if(newCount == 0){
                    charCountMap.remove(inc);
                }else{
                    charCountMap.put(inc,newCount);
                }
            }

            for(int i = 0 ; i< numCount ; i++){
                numberList.add(num);
            }
        }
        return numberList;
    }

    public static void main(String[] args){
        Map<Integer,String> numToEnglishMap = new HashMap<>();
        numToEnglishMap.put(0,"EIGHT");
        numToEnglishMap.put(1,"NINE");
        numToEnglishMap.put(2,"ZERO");
        numToEnglishMap.put(3,"ONE");
        numToEnglishMap.put(4,"TWO");
        numToEnglishMap.put(5,"THREE");
        numToEnglishMap.put(6,"FOUR");
        numToEnglishMap.put(7,"FIVE");
        numToEnglishMap.put(8,"SIX");
        numToEnglishMap.put(9,"SEVEN");

        Map<Integer,Map> numToCharMap = new HashMap<>();
        for(int num : numToEnglishMap.keySet()){
            String englishNum = numToEnglishMap.get(num);
            Map<Character,Integer> charCountMap = getCharCountMap(englishNum);
            numToCharMap.put(num,charCountMap);
        }

        Map<Character,Integer> charToSpecificNumMap = new LinkedHashMap<>();
        charToSpecificNumMap.put('G',0);
        charToSpecificNumMap.put('U',6);
        charToSpecificNumMap.put('W',4);
        charToSpecificNumMap.put('X',8);
        charToSpecificNumMap.put('Z',2);

        charToSpecificNumMap.put('O',3);
        charToSpecificNumMap.put('R',5);
        charToSpecificNumMap.put('S',9);
        charToSpecificNumMap.put('F',7);
        charToSpecificNumMap.put('I',1);
        Scanner in = new Scanner(System.in);
        int groups = in.nextInt();
        while(groups-- >0){
            String fenshen = in.next();
            Map<Character,Integer> charCountMap = getCharCountMap(fenshen);
            List<Integer> numMap = getNumberList(charCountMap,numToCharMap,charToSpecificNumMap);
            Collections.sort(numMap);

            for(int i : numMap){
                System.out.print(i);
            }
            System.out.println();
        }
    }
}

总结

解题思路1是一种很愚蠢的方式，虽然能够做出来，但是效率实在太低了，下次写代码之前还是需要进一步观察题目特征。

PS

在博客里面贴大段代码是一种很蠢的行为，但是我暂时想不到有什么比show me the code 更好的说明方式了，也许将一些无关紧要的代码用注释的方式注释出来会更好，欢迎大家给我提更好的建议。