LeetCode 12 Integer to Roman 阿拉伯数字转换为罗马数字

12. 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.

递归

通过和罗马数字比较进行转换。但是递归效率会很低，很多重复的计算

class Solution {
    public String intToRoman(int num) {
        return num >= 1000 ? "M" + intToRoman(num-1000) : 
        num >= 900 ? "CM" + intToRoman(num-900) :
        num >= 500 ? "D" + intToRoman(num-500) :
        num >= 400 ? "CD" + intToRoman(num-400) :
        num >= 100 ? "C" + intToRoman(num-100) :
        num >= 90 ? "XC" + intToRoman(num-90) :
        num >= 50 ? "L" + intToRoman(num-50) :
        num >= 40 ? "XL" + intToRoman(num-40) :
        num >= 10 ? "X" + intToRoman(num-10) :
        num >= 9 ? "IX" + intToRoman(num-9) :
        num >= 5 ? "V" + intToRoman(num-5) :
        num >= 4 ? "IV" + intToRoman(num-4) :
        num >= 1 ? "I" + intToRoman(num-1) : "";
    }
}

直接转换

递归效率很低，我们可以采用迭代的方式根据转换规则进行转换。将每一个规则看成是一个键值对。建立一个RomanMap对象。然后根据给的数字的大小，与键值对的阿拉伯数字从大到小地进行对比，然后进行转化。这里设置了一个lastPosition的变量来减少比对的顺序。虽然通过建立对象的方式效率会低一点，但是代码的可读性会增加。

class Solution {
    class RomanMap{
        int number;
        String romanNumber;
        
        RomanMap(int number,String romanNumber){
            this.number = number;
            this.romanNumber = romanNumber;
        }
        
        int getNumber(){
            return number;
        }
        
        String getRomanNumber(){
            return romanNumber;
        }
    }
    public String intToRoman(int num) {
        List<RomanMap> list = new ArrayList<RomanMap>();
        list.add(new RomanMap(1000,"M"));
        list.add(new RomanMap(900,"CM"));
        list.add(new RomanMap(500,"D"));
        list.add(new RomanMap(400,"CD"));
        list.add(new RomanMap(100,"C"));
        list.add(new RomanMap(90,"XC"));
        list.add(new RomanMap(50,"L"));
        list.add(new RomanMap(40,"XL"));
        list.add(new RomanMap(10,"X"));
        list.add(new RomanMap(9,"IX"));
        list.add(new RomanMap(5,"V"));
        list.add(new RomanMap(4,"IV"));
        list.add(new RomanMap(1,"I"));
        
        StringBuilder result = new StringBuilder();
        int lastPosition = 0; 
        
        while(num > 0 ){
            for(int i= lastPosition ;i < list.size();i++){
                RomanMap map = list.get(i);
                if(num >= map.getNumber()){
                    num -= map.getNumber();
                    result.append(map.getRomanNumber());
                    i--;
                    lastPosition = i;
                }
            }
        }
        return result.toString();
    }
}