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