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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 哈希表（一） -> 正文阅读

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

哈希表

大家好呀，我是小笙！

1.整数转罗马数字

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

罗马数字	整数
I	1
IV	4
V	5
IX	9
X	10
XL	40
L	50
XC	90
C	100
CD	400
D	500
CM	900
M	100

例子：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());
            }
        }
    }
}