Wednesday, January 7, 2015

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.
public class Solution {
    public String intToRoman(int num) {
        // Only tricky point is that 4 is “IV” not “IIII”, 9 is “IX” not “VIIII” or “VIV”.
        // First, we might think the bases are { 1000, 500, 100, 50, 10, 5, 1},
        // but if we use bases { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 },
        // this problem would become really easy.
        String ret = new String();
        
        int[] base = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        Map<Integer, String> map = new HashMap<>();
        
        map.put(1, "I");
        map.put(4, "IV");
        map.put(5, "V");
        map.put(9, "IX");
        map.put(10, "X");
        map.put(40, "XL");
        map.put(50, "L");
        map.put(90, "XC");
        map.put(100, "C");
        map.put(400, "CD");
        map.put(500, "D");
        map.put(900, "CM");
        map.put(1000, "M");
        
        for (int i : base)
        {
            while (num >= i)
            {
                ret += map.get(i);
                num -= i;
            }
        }
        
        return ret;
    }
}

No comments:

Post a Comment