首页 > 代码库 > [LeetCode] 12. Integer to Roman ☆☆

[LeetCode] 12. Integer to Roman ☆☆

 

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

 

解释:

  罗马数字采用七个罗马字母作数字、即Ⅰ(1)、X(10)、C(100)、M(1000)、V(5)、L(50)、D(500)。记数的方法:

  1. 相同的数字连写,所表示的数等于这些数字相加得到的数,如 Ⅲ=3;
  2. 小的数字在大的数字的右边,所表示的数等于这些数字相加得到的数,如 Ⅷ=8、Ⅻ=12;
  3. 小的数字(限于 Ⅰ、X 和 C)在大的数字的左边,所表示的数等于大数减小数得到的数,如 Ⅳ=4、Ⅸ=9;
  4. 在一个数的上面画一条横线,表示这个数增值 1,000 倍(本题不涉及)

  例如:整数 1437 的罗马数字为 MCDXXXVII, 我们不难发现,千位,百位,十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字,然后分别表示出来:

100 - C

200 - CC

300 - CCC

400 - CD

500 - D

600 - DC

700 - DCC

800 - DCCC

900 - CM

 

解法: 

  每次取下最高位上的数字x,判断其范围为 (0-3)、(4)、(5-8)、(9) 中的哪一类,再根据每一类的特点添加字符。

public class Solution {
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder("");
        char[] roman = {‘M‘, ‘D‘, ‘C‘, ‘L‘, ‘X‘, ‘V‘, ‘I‘};
        int[] value = http://www.mamicode.com/{1000, 500, 100, 50, 10, 5, 1};
        
        for (int i = 0; i < value.length; i += 2) {
            int x = num / value[i];
            if (x < 4) {
                while (x-- > 0) res.append(roman[i]);
            } else if (x == 4) {
                res.append(roman[i]).append(roman[i - 1]);
            } else if (x < 9) {
                res.append(roman[i - 1]);
                while (x-- > 5) res.append(roman[i]);
            } else {
                res.append(roman[i]).append(roman[i - 2]);
            }
            num %= value[i];
        }
        return res.toString();
    }
}

 

  本题由于限制了输入数字范围这一特殊性,因此也可以采用贪婪算法,建立一个数表,每次通过查表找出当前最大的数并匹配对应的字符串,然后减去再继续查表。代码如下:

public class Solution {
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder("");
        String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] value = http://www.mamicode.com/{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        for (int i = 0; i < value.length; i++) {
            int x = num / value[i];
            while (x-- > 0) res.append(roman[i]);
            num %= value[i];
        }
        return res.toString();
    }
}

 

  另外,由于限制了输入数字范围,存在的情况有限,还可以把所有的情况都列出来,然后直接按位查表,O(1)的时间复杂度,代码如下:

public class Solution {
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder("");
        String[] r1 = {"", "M", "MM", "MMM"};
        String[] r2 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] r3 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] r4 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        
        res.append(r1[num / 1000]).append(r2[(num % 1000) / 100]).append(r3[(num % 100) / 10]).append(r4[(num % 10) / 1]);
        return res.toString();
    }
}

 

[LeetCode] 12. Integer to Roman ☆☆