問題

Given an integer, convert it to a roman numeral.

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

例子

MMXVII
2017

分析

鑒于輸入數(shù)字的范圍為[1,3999]，可以把數(shù)字拆成個十百千四位來看。建立四張映射表，把四位數(shù)字映射到對應的羅馬數(shù)字即可。

• 個位："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]

要點

• 理解羅馬數(shù)字和阿拉伯數(shù)字的對應關系；
• 數(shù)字位映射。

時間復雜度

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];
    }
};