12. Integer to Roman

问题

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

例子

MMXVII
2017

分析

鉴于输入数字的范围为[1,3999]，可以把数字拆成个十百千四位来看。建立四张映射表，把四位数字映射到对应的罗马数字即可。

• 个位："I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" [1-9]
• 十位："X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" [10-90]
• 百位："C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" [100-900]
• 千位："M", "MM", "MMM" [1000-3000]

要点

• 理解罗马数字和阿拉伯数字的对应关系；
• 数字位映射。

时间复杂度

O(1)

空间复杂度

O(1)

代码

class Solution {
public:
    string intToRoman(int num) {
        // 注意个十百千四位的映射表都有一个空字符串，为了处理当该位为0的情况
        vector<string> thousands{"", "M", "MM", "MMM"};
        vector<string> houdreds{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> tens{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> ones{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return thousands[num / 1000] + houdreds[(num % 1000) / 100] + 
            tens[(num % 100) / 10] + ones[num % 10];
    }
};