12. 整数转罗马数字

Problem: 12. 整数转罗马数字

思路

模拟题目所说罗马数字转换规则即可。另外，实际上不需要判断数字以哪位开头，因为每次选择选项中最大的那个时，自然会满足题目所说的转换规则。

另外，由于情况是有限的，可以给每个位的情况都列一个表，这样时间复杂度是$O(1)$。

复杂度

• 时间复杂度: $O(n)$，n为num位数。
• 空间复杂度: $O(1)$。

Code

class Solution {
    public String intToRoman(int num) {
        int [] values = {1000, 900, 500, 400, 100 , 90, 50, 40, 10, 9, 5, 4, 1};
        String [] svalues = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; 
        String s = Integer.toString(num);
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            for (int i = 0; i < 13; i++) {
                if (num >= values[i]) {
                    sb.append(svalues[i]);
                    num -= values[i];
                    break;
                }
            }
        }
        return sb.toString();
    }
}