1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String intToRoman(int num) {
        int[] values = new int[] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] symbols = new String[] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                ans.append(symbols[i]);
            }
        }
        return ans.toString();
    }
}

最大的启发就是, 实在不行, hardcode吧.
这个思路很简单, 先往大的挑, 看能减不, 然后减到不能减再挑次大的减, 以此类推, 直到减完.

时间复杂度: O(1)
空间复杂度: O(1)