长大后想做什么？做回小孩！

0%

LeetCode——罗马数字转整数

发表于 更新于 分类于 Valine：
本文字数： 249

NO.13 罗马数字转整数 简单

Q4As2Q.png

Q4Ar8g.png

思路一：哈希表 1.用一个hash表把所有罗马数字和阿拉伯数字相互匹配的特殊值作为键值对存储起来，例如”M,1000”、”CM,900”、”D,500”、”CD，400”。。。2.然后将字符串逐步分割并去hash表进行查询匹配，因为两位长度的罗马数字优先于一位长度的罗马数字，所以每步循环都需要先两位分割匹配再一位分割匹配。3.匹配到hash表的键之后，将对应的值加入结果中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int romanToInt(String s) {
        int ans=0;
//        所有罗马数字和阿拉伯数字相互匹配的特殊值作为键值对存储起来
        Map<String,Integer> map=new HashMap<>();
        map.put("M",1000);
        map.put("CM",900);
        map.put("D",500);
        map.put("CD",400);
        map.put("C",100);
        map.put("XC",90);
        map.put("L",50);
        map.put("XL",40);
        map.put("X",10);
        map.put("IX",9);
        map.put("V",5);
        map.put("IV",4);
        map.put("I",1);
//        然后将字符串逐步分割并去hash表进行查询匹配
        for (int i=0;i<s.length(); ){
//            两位长度的罗马数字优先于一位长度的罗马数字,所以先进行两位长度罗马数字的判断
            if (i+1<s.length()&&map.containsKey(s.substring(i,i+2))){
                ans+=map.get(s.substring(i,i+2));
                i+=2;
            }else {
                ans+=map.get(s.substring(i,i+1));
                i++;
            }
        }
        return ans;
    }

时间复杂度:O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github