12.整数转罗马数字

贪心

罗马数字的构造规则本质上就是每次优先使用当前能表示的最大数值符号，因此可以直接按照从大到小的顺序不断选取。

例如遇到 $1994$ 时，先取 $1000$ 对应的 $M$，剩余 $994$；再取 $900$ 对应的 $CM$，剩余 $94$；再取 $90$ 对应的 $XC$，最后取 $4$ 对应的 $IV$。这样依次拼接即可得到答案。

由于题目中所有可能用到的数值组合都是固定的，因此只需要把这些值按从大到小列出来，遍历时不断减去并拼接对应符号即可。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

class Solution {
    private static final Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
    static {
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");
    }
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            int value = entry.getKey();
            String symbol = entry.getValue();

            while (num >= value) {
                sb.append(symbol);
                num -= value;
            }
        }
        return sb.toString();
    }
}

数组模拟

上面的写法思路很直接，不过这里其实并不需要真的使用 Map，因为所有数值和符号都是固定顺序的，直接用两个数组一一对应即可。

遍历 values 数组时，如果当前数值还能从 num 中减去，就把对应的罗马字符加入答案，并继续减去，直到不能再减为止。由于可选项只有固定的 $13$ 个，所以整体仍然是常数时间。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"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) {
            int value = values[i];
            String symbol = symbols[i];

            while (num >= value) {
                sb.append(symbol);
                num -= value;
            }
        }
        return sb.toString();
    }
}