[数据结构与算法]哈希表（一）

哈希表

大家好呀，我是小笙！

1.整数转罗马数字

整数转换成罗马数字之间存在键值对的关系

例子：27 写做 XXVII, 即为 XX + V + II

我的暴力解法

思路：

• 先用键值对保存整数和罗马数字之间的关系
• 通过每次循环找到可以相减的最大数，这样子就可以获取到最终的值

class Solution {
    public String intToRoman(int num) {
        Map<Integer,String> map = new HashMap<>();
        map.put(1,"I");
        map.put(4,"IV");
        map.put(5,"V");
        map.put(9,"IX");
        map.put(10,"X");
        map.put(40,"XL");
        map.put(50,"L");
        map.put(90,"XC");
        map.put(100,"C");
        map.put(400,"CD");
        map.put(500,"D");
        map.put(900,"CM");
        map.put(1000,"M");
        // 使用 StringBuilder 是因为在单线程中 StringBuilder 对增加字符串性能是最好的效率最高
        StringBuilder sb = new StringBuilder();
        while(num != 0){
            if(num >= 1000){
                sb.append(map.get(1000)); 
                num -= 1000;
            }else if(num >= 900){
                sb.append(map.get(900)); 
                num -= 900;
            }else if(num >= 500){
                sb.append(map.get(500)); 
                num -= 500;
            }else if(num >= 400){
                sb.append(map.get(400)); 
                num -= 400;
            }else if(num >= 100){
                sb.append(map.get(100)); 
                num -= 100;
            }else if(num >= 90){
                sb.append(map.get(90)); 
                num -= 90;
            }else if(num >= 50){
                sb.append(map.get(50)); 
                num -= 50;
            }else if(num >= 40){
                sb.append(map.get(40)); 
                num -= 40;
            }else if(num >= 10){
                sb.append(map.get(10)); 
                num -= 10;
            }else if(num >= 9){
                sb.append(map.get(9)); 
                num -= 9;
            }else if(num >= 5){
                sb.append(map.get(5)); 
                num -= 5;
            }else if(num >= 4){
                sb.append(map.get(4)); 
                num -= 4;
            }else if(num >= 3){
                sb.append("III"); 
                num -= 3;
            }else if(num >= 2){
                sb.append("II"); 
                num -= 2;
            }else if(num >= 1){
                sb.append("I"); 
                num -= 1;
            }
        }
        return new String(sb);
    }
}

优化思路

由于重复代码太多（代码繁琐），我改用循环遍历解决

核心思想就是这么多个值我改用数组代替，但是效率甚至不如之前

class Solution {
    public String intToRoman(int num) {
        int[] nums = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        Map<Integer,String> map = new HashMap<>();
        map.put(1,"I");
        map.put(4,"IV");
        map.put(5,"V");
        map.put(9,"IX");
        map.put(10,"X");
        map.put(40,"XL");
        map.put(50,"L");
        map.put(90,"XC");
        map.put(100,"C");
        map.put(400,"CD");
        map.put(500,"D");
        map.put(900,"CM");
        map.put(1000,"M");
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<nums.length;i++){
            String key = map.get(nums[i]);
            while(num >= nums[i]){
                sb.append(key);
                num -= nums[i];
            }
            if(num == 0){
                break;
            }
        }
        return new String(sb);
    }
}

终极代码（模仿官方）暴力解码

核心理念：就是列出 千位 百位 十位 各位 所有可能，只需要进行一次匹配进行，效率极高

class Solution {
    String[] thousands = {"", "M", "MM", "MMM"};
    String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }
}

2.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合，就是老式电话上数字对应字母，用字母拼凑出所有字母的情况（长度就是数字的数量），但是是有顺序的，第一个数字出现的字母位置必须在第一个以此类推，长度最长为4

上来我就是一顿暴力解法,一开始我考虑多半会运行超时，但是没有，所以我就“搬出来”给大家看一下

class Solution {
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        List<String> res = new ArrayList<>();
        if(len == 0){
            return res;
        }else{
            Map<Character,String> map = new HashMap<>();
            map.put('2',"abc");
            map.put('3',"def");
            map.put('4',"ghi");
            map.put('5',"jkl");
            map.put('6',"mno");
            map.put('7',"pqrs");
            map.put('8',"tuv");
            map.put('9',"wxyz");
            char[] chs = new char[len];
            for(int i=0;i<len;i++){
                chs[i] = digits.charAt(i);
            }
            if(len == 1){
                String str = map.get(chs[0]);
                for(int i=0;i<str.length();i++){
                    res.add("" + str.charAt(i));
                }
                return res;
            }else if(len == 2){
                String str = map.get(chs[0]);
                String str1 = map.get(chs[1]);
                for(int i=0;i<str.length();i++){
                    for(int j=0;j<str1.length();j++){
                        res.add("" + str.charAt(i) + str1.charAt(j));
                    }
                }
                return res;
            }else if(len == 3){
                String str = map.get(chs[0]);
                String str1 = map.get(chs[1]);
                String str2 = map.get(chs[2]);
                for(int i=0;i<str.length();i++){
                    for(int j=0;j<str1.length();j++){
                        for(int k=0;k<str2.length();k++){
                            res.add("" + str.charAt(i) + str1.charAt(j) + str2.charAt(k));
                        }
                    }
                }
                return res;
            }else if(len == 4){
                String str = map.get(chs[0]);
                String str1 = map.get(chs[1]);
                String str2 = map.get(chs[2]);
                String str3 = map.get(chs[3]);
                for(int i=0;i<str.length();i++){
                    for(int j=0;j<str1.length();j++){
                        for(int k=0;k<str2.length();k++){
                            for(int m=0;m<str3.length();m++){
                                res.add("" + str.charAt(i) + str1.charAt(j) + str2.charAt(k) + str3.charAt(m) );
                            }
                        }
                    }
                }
                return res;
            }
            return res;
        }
    }
}

优化，从代码整洁上考虑，太多的冗余代码,使用递归来解决代码复用，同时运行速度从 13ms 到 1ms，效率提升还是很明显的

class Solution {
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        List<String> res = new ArrayList<>();
        if(len == 0){
            return res;
        }else{
            Map<Character,String> map = new HashMap<>();
            map.put('2',"abc");
            map.put('3',"def");
            map.put('4',"ghi");
            map.put('5',"jkl");
            map.put('6',"mno");
            map.put('7',"pqrs");
            map.put('8',"tuv");
            map.put('9',"wxyz");
            char[] chs = new char[len];
            String[] n = new String[len];
            for(int i=len-1;i>=0;i--){
                n[i] = map.get(digits.charAt(len-i-1));
            }
            cicle(res,len,n,new StringBuilder());
            return res;
        }
    }

    // String[] n 指的是倒叙对应数字对应的字母 比如 24 对应 ["ghi","abc"]
    public void cicle(List<String> list,int len,String[] n,StringBuilder str){
        if(len == 1){
            for(int i=0;i<=n[len-1].length()-1;i++){
                str.append("" + n[len-1].charAt(i));
                list.add(new String(str));  
                str.delete(str.length()-1,str.length());
            }
            return;
        }else{
            for(int i=0;i<=n[len-1].length()-1;i++){
                str.append("" + n[len-1].charAt(i)); 
                cicle(list,len-1,n,str);
                str.delete(str.length()-1,str.length());
            }
        }
        return;
    }
}

这个时候停止优化吗？不，我们还需要提升在算法性能，内存上达到超过90%，这是我现在所能做到最好的

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        // 简化 map 添加值
        Map<Character, String> map = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        String[] n = new String[len];
        for(int i=len-1;i>=0;i--){
            n[i] = map.get(digits.charAt(len-i-1));
        }
        cicle(len,n,new StringBuilder());
        return res;
    }

    // 简化递归算法的重复代码，极简化，而且不影响效率
    public void cicle(int len,String[] n,StringBuilder str){
        if(len > 0){
            for(int i=0;i<=n[len-1].length()-1;i++){
                str.append("" + n[len-1].charAt(i)); 
                if(len > 1){
                    cicle(len-1,n,str);
                }else{
                    res.add(new String(str));  
                }
                str.delete(str.length()-1,str.length());
            }
        }
    }
}