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.
题目翻译
将整数转化成罗马数字，其中输入数据范围是1到3999
解题方案
标签： 数学, 字符串
思路：
- 罗马数字的计数方法:
| 罗马字符 | I | V | X | L | C | D | M |
|---|---|---|---|---|---|---|---|
| 整数数字 | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
- 相同的数字连写，所表示的数等于这些数字相加得到的数，如：III = 3； 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：VIII = 8；XII = 12；
- 小的数字，（限于I、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：IV= 4；IX= 9；
- 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外） 在一个数的上面画一条横线，表示这个数扩大1000倍。（本题用不到这点）
有几条须注意掌握：
- 基本数字I、X、C中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
- 不能把基本数字V、L、D中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
- V和X左边的小数字只能用I，且只能有1个。
- L和C左边的小数字只能用X，且只能有1个。
- D和M左边的小数字只能用C，且只能有1个。 看懂了上面的规则后，就可以对数字的每位逐个判断即可。可以归纳出如下4种情形：
如果该位数字是9，则说明是上面3、4、5这三种情况中的一种，即把I、X、C中的一个放到了大数字的左侧； 如果该位数字是5~8，则说明是上面1这种情况，即I、X、C中的一个，自身连用或者放在大数的右边连用； 如果该位数字是4，则说明同样是上面3、4、5这三种情况中的一种，即把I、X、C中的一个放到了大数字的左侧； 如果该位数字是0~3，则同样说明是上面1这种情况，即I、X、C中的一个，自身连用或者放在大数的右边连用。 时间复杂度：O(n)
空间复杂度：O(1)
代码：
class Solution
{
public:
string intToRoman(int num)
{
int n[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string r[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string s = "";
for(int i = 0; num > 0; num %= n[i], ++ i)
for(int j = 0, k = num / n[i]; j < k; ++ j)
s += r[i];
return s;
}
};