LeetCode 012 Integer to Roman

Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, two is written as

II

in Roman numeral, just two one’s added together. Twelve is written as,

XII

, which is simply

X + II

. The number twenty seven is written as

XXVII

, which is

XX + V + II

.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not

IIII.

Instead, the number four is written as

IV

. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as

IX

. There are six instances where subtraction is used:

• I

  can be placed before

  V

  (5) and

  X

  (10) to make 4 and 9.

• X

  can be placed before

  L

  (50) and

  C

  (100) to make 40 and 90.

• C

  can be placed before

  D

  (500) and

  M

  (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"


Example 2:

Input: 4
Output: "IV"


Example 3:

Input: 9
Output: "IX"


Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.


Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

           

题目分析

很简单的一个题，就是把阿拉伯数字改写成罗马数字表示。规则需要注意，类似4，40，9，90这种的数字表示时需要用后面的数字来减前面的数，题目中讲的很清楚。出题范围在（1,3999），所以万位以上的数字可以不考虑。

另，由于频繁的增加字符串，建议使用StringBuilder，返回时转成字符串返回。

public String intToRoman(int num) {
        StringBuilder output = new StringBuilder("");
        int temp = 0;
        //千位转换
        if (num >= 1000) {
            temp = num / 1000;
            for (int i = 0; i < temp; i++) {
                output.append("M");
            }
            num = num % 1000;
        }
        //百位转换
        if (num >= 900) {
            output.append("CM");
            num -= 900;
        }
        if (num >= 500 && num < 900) {
            output.append("D");
            temp = (num - 500) / 100;
            for (int i = 0; i < temp; i++) {
                output.append("C");
            }
            num = num % 100;
        }
        if (num >= 400 && num < 500) {
            output.append("CD");
            num -= 400;
        }
        if (num >= 100 && num < 400) {
            temp = num / 100;
            for (int i = 0; i < temp; i++) {
                output.append("C");
            }
            num = num % 100;
        }

        //十位转换
        if (num >= 90) {
            output.append("XC");
            num -= 90;
        }
        if (num >= 50 && num < 90) {
            output.append("L");
            temp = (num - 50) / 10;
            for (int i = 0; i < temp; i++) {
                output.append("X");
            }
            num = num % 10;
        }
        if (num >= 40 && num < 50) {
            output.append("XL");
            num -= 40;
        }
        if (num >= 10 && num < 40) {
            temp = num / 10;
            for (int i = 0; i < temp; i++) {
                output.append("X");
            }
            num = num % 10;
        }

        //个位转换
        if (num == 9) {
            output.append("IX");
            num -= 90;
        }
        if (num >= 5 && num < 9) {
            output.append("V");
            temp = num - 5;
            for (int i = 0; i < temp; i++) {
                output.append("I");
            }
        }
        if (num == 4) {
            output.append("IV");
        }
        if (num < 4) {

            for (int i = 0; i < num; i++) {
                output.append("I");
            }
        }

        return output.toString();

    }
           

然后其实三块的代码都是重复代码，区别只在于数字的范围和字符串中增加的字符。

故可以优化将他们抽象成一个函数来表示。

public String intToRoman(int num) {
        StringBuilder res = new StringBuilder();
        
        int quotient = num / 1000;
        for (int i=0; i<quotient; i++)
            res.append('M');
        
        num = num % 1000;
        
        while (num > 0){
            if (num >= 100){
                convertToRoman(num, 100, 'C', 'D', 'M', res);
                num %= 100;
            }
            if (num >= 10){
                convertToRoman(num, 10, 'X', 'L', 'C', res);
                num %= 10;
            }
            
            if (num >= 1){
                convertToRoman(num, 1, 'I', 'V', 'X', res);
                num -= 10;
            }
        }
        
        return res.toString();
    }
    
    // param1 stands 1, param2 stands 5, param3 stands 10.
    public StringBuilder convertToRoman(int num, int digit, char param1, char param2, char param3, StringBuilder str){
        int quotient = num / digit;

        if (quotient > 5){
            if (quotient < 9){
                str.append(param2);
                for (int i=0; i<quotient-5; i++)
                    str.append(param1);
            }else{
                str.append(param1);
                str.append(param3);
            }
        }else{
            if (quotient == 5)
                str.append(param2);
            else if (quotient == 4){
                str.append(param1);
                str.append(param2);
            }else {
                for (int i=0; i<quotient; i++)
                    str.append(param1);
            }
        }

        return str;
    }