Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
class Solution {
public:
string intToRoman(int num) {
char symbol[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
int i = 6;
int weight = 1000;
string result;
while (num) {
const int digit = num / weight;
if (digit <= 3) {
result.append(digit, symbol[i]);
}
else if (digit == 4) {
result.append(1, symbol[i]);
result.append(1, symbol[i+1]);
}
else if (digit == 5) {
result.append(1, symbol[i+1]);
}
else if (digit <= 8) {
result.append(1, symbol[i+1]);
result.append(digit-5, symbol[i]);
}
else {
result.append(1, symbol[i]);
result.append(1, symbol[i+2]);
}
num %= weight;
weight /= 10;
i -= 2;
}
return result;
}
};
此题的关键是对罗马数字规则的理解。
罗马数字虽然有七个基本字符，但我觉得对规则的理解可以从I和V两个字符开始。
I表示1，V表示5.
如何表示阿拉伯数字1-9呢？
1~3， 可以用I来凑数。如I，II, III
4呢，那就5-1， IV （左边的数字较小则为减）。
5，就是 V
6~8，则用5+， 即先用一个V，不够的用I来凑数， 如VI, VII, VIII。
9的话，10-1，10就得依靠下一组罗马数字帮忙了。
下一组就是 10，50，
再下一组就是 100， 500，
但组数规则和I V是一样的，只是符号不一样，代表的权重不一样。
IV负责个位数
XL负责十位数
CD负责百位数
MV负责千位数
XL负责万位数
CD负责十万位数
...
此题目考到3999为止，大概是因为从4000开始，就得用到带上划线的字符了。
上面的算法的思路比较大众。
为了加深对罗马数字转换的理解，我写了另外一个与众不同的算法，此算法看起来，比上一个要略复杂。
class Solution {
public:
string intToRoman(int num) {
char symbol[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
int i = sizeof(symbol)/sizeof(symbol[0]) - 1;
string result;
while (num) {
const int w = weight(i);
while (num >= w) { // handle 1,2,3 ,5,6,7,8 ...
result.append(1, symbol[i]);
num -= w;
}
if (i) {
const int one = i - (i+1)%2 - 1;
const int w4 = w - weight(one);
if (num >= w4) { // handle 4, 9 ...
result.append(1, symbol[one]);
result.append(1, symbol[i]);
num -= w4;
}
i--;
}
}
return result;
}
inline int weight(int i) {
return pow(5, i%2) * pow(10, i/2);
}
};
与第一个算法相比，此算法主要特点为，只需要特殊处理，4， 9， 40， 90， 400， 900这一类情况。
即总共两种case。