leetcode12.十进制数转化为罗马数字

发表于 更新于 分类于 ，

这是罗马数字转为十进制数的后序
题目要求：将十进制数字转化为罗马数字，数值范围是[1,3999]
在罗马数字转化为十进制数的博客中,我简单的介绍了一下如何将罗马数字转化为十进制数字。在这道题目里，我们需要进一步了解十进制数转换为罗马数字的协议

  1. 罗马单个数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）
  2. 可以被减去的值只有I（1)、X（10）、C（100）,且每个值最多只可以减去一次
  3. 左减时不可以跨位数，例如99不能被表示为IC,而是XCIX
  4. 多个相同字母连续出现时表示相加，但是字母不能重复出现超过4次

综上所述，个位上的数可以由I、V、X表示出来，同理，十位上的树可以由X、L、C表示，百位上可以由C、D、M表示，千位上则为M（数字不超过3999）
所以可以分别对整数的每一位上的值进行计算，得出相应的罗马数字值，并最后合并为最终得罗马数字

思路一：遍历每一位的值转换为罗马数字

我尝试了两种数据存储方法，先尝试了map，感觉性能较差，然后尝试了array，性能的提升并不显著

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//map
public String intToRoman(int num) {
    Map<Integer, Character> romanIntMap = new HashMap<Integer, Character>();
    romanIntMap.put(1, 'I');
    romanIntMap.put(5, 'V');
    romanIntMap.put(10, 'X');
    romanIntMap.put(50, 'L');
    romanIntMap.put(100, 'C');
    romanIntMap.put(500, 'D');
    romanIntMap.put(1000, 'M');
    StringBuilder finalResult = new StringBuilder();
    for(int i = 1 ; num>0 ; i*=10){
        StringBuilder result = new StringBuilder("");
        int digit = num%10;

        if(digit==0){
            
        }else if(digit<=3){
            for(int j = 0 ; j<digit ; j++){
                result.append(romanIntMap.get(i));
            }
        }else if(digit==4){
            result.append(romanIntMap.get(i*5));
            result.append(romanIntMap.get(i));
        }else if(digit==5){
            result.append(romanIntMap.get(i*5));
        }else if(digit<=8){
            for(int j = 0 ; j<digit-5 ; j++){
                result.append(romanIntMap.get(i));
            }
            result.append(romanIntMap.get(i*5));
        }else{
            result.append(romanIntMap.get(i*10));
            result.append(romanIntMap.get(i));
        }
        finalResult.insert(0,result.reverse());
        num /= 10;
    }
    return finalResult.toString();
}

//数组
public String intToRoman2(int num){
    char[] romans = new char[]{'I','V','X','L','C','D','M'};
    StringBuilder finalResult = new StringBuilder();
    for(int i = 0 ; num>0 ; i++){
        StringBuilder result = new StringBuilder("");
        int digit = num%10;
        num /= 10;
        if(digit==0){
            continue;
        }else if(digit<=3){
            for(int j = 0 ; j<digit ; j++){
                result.append(romans[i*2]);
            }
        }else if(digit==4){
            result.append(romans[i*2+1]);
            result.append(romans[i*2]);
        }else if(digit==5){
            result.append(romans[i*2+1]);
        }else if(digit<=8){
            for(int j = 0 ; j<digit-5 ; j++){
                result.append(romans[i*2]);
            }
            result.append(romans[i*2+1]);
        }else{
            result.append(romans[i*2+2]);
            result.append(romans[i*2]);
        }
        finalResult.insert(0,result.reverse());
        
    }
    return finalResult.toString();
}

思路二：穷尽枚举

因为题设中输入罗马数字是一定区间上的值，因此它的特殊情况是可以穷尽的
我们从个位入手来考虑每一位上较为特殊的情况

  • ==9 : IX
  • ==5 : V
  • ==4 : IV
  • <4 : I*n
    也就是说，由大至小减去后剩下的值都有对应的罗马数字存在
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String intToRoman(int num) {
    int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    StringBuilder sb = new StringBuilder();

    for(int i=0;i<values.length;i++) {
        while(num >= values[i]) {
            num -= values[i];
            sb.append(strs[i]);
        }
    }
    return sb.toString();
}