Integer to Roman

Integer to Roman

 

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

Naive Way:还是先写几个例子。
Integer    Roman
1             I
2             II
3             III
4             IV
5             V
6             VI
7             VII
8             VIII
9             IX
10            X
11            XI
14            XIV
15            XV
18            XVIII
19            XIX
21            XXI

可以采用不断取最高位的方法，一旦余数是9，4倍下一级的，就要单独处理。

我的做法是，每一次除当前位的同时都除以下一位看是不是9。考虑到45/5 = 9，45/10 = 4...5这种情况，4的优先级比9高。

public class Solution {
    private static final char[] syms = {'I','V','X','L','C','D','M'};
    private static final int[] val = {1,5,10,50,100,500,1000}; 
    public String intToRoman(int num) {
        String s = "";
        int i = val.length-1;
        while(num!=0){
            int cur = num/val[i];
            int low = i > 0?num/val[i-1]:0;
            if(cur!=0){
                if(cur==4){
                    s += syms[i];
                    s += syms[i+1];
                    num %=val[i];
                }else if(low==9){
                    s += syms[i-1];
                    s += syms[i+1];
                    num %=val[i-1];
                }else{
                    for(int j =0;j < cur;j++)
                        s += syms[i];
                    num %=val[i];
                }
            }
            i--;
        }
        return s;
    }
}

Improved Way:discuss里的方法真是千奇百怪啊，各种数组。下面有三种方法是我觉得最好玩的。

 

一、 来自leetcode的 jakwings用户。[[1 5], [10 50]]这样的排成二维数组，巧妙将4和9化为同一等级。

 

class Solution {
public:
    vector<vector<string>> table = {
        {"I", "V"},
        {"X", "L"},
        {"C", "D"},
        {"M", "~V"}  // ~V = 1000 * V
    };
    string intToRoman(int num) {
        if (num <= 0) return "";
        vector<int> digits;
        for (int t = num; t != 0; t /= 10) {
            digits.push_back(t % 10);
            int i = digits.size() + 1;
            if (table.size() < i) {
                table.push_back({'~' + table[i-3][0], '~' + table[i-3][1]});
            }
        }
        string result;
        for (int i = digits.size() - 1; i >= 0; i--) {
            int x = digits[i];
            switch (x) {
            case 0: break;
            case 9: result += table[i][0] + table[i+1][0]; break;
            case 4: result += table[i][0] + table[i][1]; break;
            default:
                if (x >= 5) result += table[i][1];
                for (int j = x % 5; j > 0; j--) result += table[i][0];
            }
        }
        return result;
    }
};

 

二、来自leetcode用户 flytosky ,将所有所有可能出现的单个都列了一遍，因为本来1~10也才10个数，到1000也才30个数。这个方法我觉得最牛了。

 

string intToRoman(int num) {
    string M[] = {"", "M", "MM", "MMM"};
    string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}

 三、来自leetcode用户magicknife，也是discuss里少有的用recursive去做的，将4， 9也看成一个符号。这样每一个10位就有1 4 5 9 四种符号。

 

 

public class Solution {

    private static LinkedHashMap<Integer, String> numToRoman = new LinkedHashMap<Integer, String>();
    static {
        numToRoman.put(1000, "M");
        numToRoman.put(900, "CM");
        numToRoman.put(500, "D");
        numToRoman.put(400, "CD");
        numToRoman.put(100, "C");
        numToRoman.put(90, "XC");
        numToRoman.put(50, "L");
        numToRoman.put(40, "XL");
        numToRoman.put(10, "X");
        numToRoman.put(9, "IX");
        numToRoman.put(5, "V");
        numToRoman.put(4, "IV");
        numToRoman.put(1, "I");
    }
    public String intToRoman(int num) {
        for (Integer i : numToRoman.keySet()) {
            if (num >= i) {
                return numToRoman.get(i) + intToRoman(num - i);
            }
        }
        return "";
    }
}