1 问题

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1

输入: num = 3
输出: “III”
示例 2
输入: num = 4
输出: “IV”
示例 3
输入: num = 9
输出: “IX”
示例 4
输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5
输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示

1 <= num <= 3999

2 解题思路

以题目中num的界限为基准，阿拉伯数字的表示形式为：
num=a*1000+b*100+c*10+d.

2.1 解法一

类似阿拉伯数字的表示形式，罗马的表示形式可以为：
num=a*M+b*C+c*X(或c*L)+d*I，但是有所不同的是，对于百位和十位，罗马数字有不同的表示方式，因而我们可以把各个位上的基础数字表示完整，通过阿拉伯数字的表示形式，计算出各个位的有多少因子即可。

比如：百位的基数罗马数字可以用String数组表示：
String[] hrns = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};。

hrns可以将百位上的数表示完整，即100、200、300、…、900，hrns[0]表明百位上可能为0。其他位类似表示。

详见代码中的解法一。

2.2 解法二

类似2.1中的表示形式，我们可以列举出罗马数字的所有基础数字，即：

String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

表示数字为1000，900，500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1。罗马数字只能由strs数组中的字符表示出来。

因而，我们可以把数字表示成：有几个M，有几个CM，…, 以此类推。只是这里可以通过减法去做。

详见代码中的解法二。

3 代码

class Solution {
    //0-9 d
    String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    //10-90 c
    String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    //100-900 b
    String[] hrns = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    //1000-3000 a
    String[] ths = {"", "M", "MM", "MMM"};

    //    解法一
    public String intToRoman2(int num) {
        //num=a*1000+b*100+c*10+d
        return ths[num / 1000] + hrns[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
    }


    //    解法二
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(strs[i]);
            }
        }
        return sb.toString();
    }
}