羅馬數(shù)字包含以下七種字符： I赦拘， V甸各， X垛贤， L，C趣倾，D 和 M聘惦。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II 儒恋，即為兩個(gè)并列的 1善绎。12 寫做 XII ，即為 X + II 诫尽。 27 寫做 XXVII, 即為 XX + V + II 禀酱。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊箱锐。但也存在特例比勉，例如 4 不寫做 IIII劳较，而是 IV驹止。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 观蜗。同樣地臊恋，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊墓捻，來(lái)表示 4 和 9抖仅。
X 可以放在 L (50) 和 C (100) 的左邊，來(lái)表示 40 和 90砖第。
C 可以放在 D (500) 和 M (1000) 的左邊撤卢，來(lái)表示 400 和 900。
給你一個(gè)整數(shù)梧兼，將其轉(zhuǎn)為羅馬數(shù)字放吩。
示例 1:
輸入: num = 3
輸出: "III"
思路一：暴力解法
每次減去最大值
string intToRoman(int num) {
string s;
while (num >= 1000)
{
s += 'M';
num -= 1000;
}
if (num >= 900)
{
s += "CM";
num -= 900;
}
if (num >= 500)
{
s += "D";
num -= 500;
}
if (num >= 400)
{
s += "CD";
num -= 400;
}
while (num >= 100)
{
s += 'C';
num -= 100;
}
if (num >= 90)
{
s += "XC";
num -= 90;
}
if (num >= 50)
{
s += 'L';
num -= 50;
}
if (num >= 40)
{
s += "XL";
num -= 40;
}
while (num >= 10)
{
s += 'X';
num -= 10;
}
if (num >= 9)
{
s += "IX";
num -= 9;
}
if (num >= 5)
{
s += 'V';
num -= 5;
}
if (num >= 4)
{
s += "IV";
num -= 4;
}
while (num >= 1)
{
s += 'I';
num -= 1;
}
return s;
}
思路二：使用數(shù)組來(lái)處理
1）構(gòu)建數(shù)組存儲(chǔ)數(shù)值從1000到1
2）構(gòu)建字符串?dāng)?shù)組存儲(chǔ)從1000到1的羅馬數(shù)字
3）使用while循壞，每次減去最大值羽杰，并保存轉(zhuǎn)換的結(jié)果
string intToRoman(int num) {
int nums[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
vector<string> s = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int index = 0;
string res = ""; //保存轉(zhuǎn)換的結(jié)果
while(index <13){ //從頭減到尾
while(num >= nums[index]){ //每次都減去最大值
res += s[index];
num -= nums[index];
}
index++;
}
return res;
}
