2015-06-03
罗马数字以前接触过I到VIII比较多，直到遇见这个题目才知道更详细。阿拉伯数字和罗马数字之间的转换最重的是了解罗马数字的规则。
罗马数字规则：（总结）
1， 罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。
罗马数字中没有“0”。
2， 重复次数：一个罗马数字最多重复3次。
3， 右加左减：
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
4， 左减的数字有限制，仅限于I、X、C，且放在大数的左边只能用一个。
(*) V 和 X 左边的小数字只能用Ⅰ。
(*) L 和 C 左边的小数字只能用X。
(*) D 和 M 左 边的小数字只能用C。
Roman to integer
Given a roman numeral,convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.
两种 C++ solution
1、
class Solution {
public:
int romanToInt(string s) {
int res=0;
int lastValue=0;
int digit;
for(int i=s.size()-1;i>=0;i--){
switch(s[i]){
case 'I': digit=1; break;
case 'V': digit=5; break;
case 'X': digit=10; break;
case 'L': digit=50; break;
case 'C': digit=100; break;
case 'D': digit=500; break;
case 'M': digit=1000; break;
}
if(digit>=lastValue){
res+=digit;
lastValue=digit;
}
else res-=digit;
}
return res;
}
};
或： Problem is simpler to solve by working the string from back to front and using a map. Runtime speed is 56 ms.
2、
class Solution {
public:
int romanToInt(string s)
{
unordered_map<char, int> T = { { 'I' , 1 },
{ 'V' , 5 },
{ 'X' , 10 },
{ 'L' , 50 },
{ 'C' , 100 },
{ 'D' , 500 },
{ 'M' , 1000 } }; int sum = T[s.back()];
for (int i = s.length() - 2; i >= 0; --i)
{
if (T[s[i]] < T[s[i + 1]])
{
sum -= T[s[i]];
}
else
{
sum += T[s[i]];
}
} return sum;
}
};
Integer to Roman
Given an integer,convert it to a roman numeral.Input is guaranteed tobe within the range from 1 to 3999.
1、16ms c++ solution
class Solution {
public:
const static string THOUS[];
const static string HUNDS[];
const static string TENS[];
const static string ONES[];
string intToRoman(int num) {
string result;
result += THOUS[(int)(num/1000)%10];
result += HUNDS[(int)(num/100)%10];
result += TENS[(int)(num/10)%10];
result += ONES[num%10];
return result;
}
};
const string Solution::THOUS[] = {"","M","MM","MMM"};
const string Solution::HUNDS[] = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
const string Solution::TENS[] = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
const string Solution::ONES[] = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
2、 44ms c++ solution
class Solution {
public:
string intToRoman(int num) {
vector<pair<string, int> > mp { {"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100}, {"XC", 90}, {"L", 50}, {"XL", 40}, {"X", 10}, {"IX", 9}, {"V", 5}, {"IV", 4}, {"I", 1} };
string result;
while (num) {
for (auto p : mp) {
if (num >= p.second) {
result += p.first, num -= p.second;
break;
}
}
}
return result;
}
};