問題
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
例子
2017
MMXVIII
分析
- 方法一：可以參考12. Integer to Roman映射表的思路，建立羅馬數(shù)字到阿拉伯數(shù)字的映射表。映射表中的羅馬數(shù)字的順序從大到小排序肥惭。遍歷并切割字符串，依次和映射表中的羅馬數(shù)字匹配忍饰，把匹配結(jié)果累加即可。映射表如下：
vector<pair<string, int>> s2i{{"MMM", 3000}, {"MM", 2000}, {"M", 1000},
{"CM", 900}, {"DCCC", 800}, {"DCC", 700}, {"DC", 600}, {"D", 500}, {"CD", 400}, {"CCC", 300}, {"CC", 200}, {"C", 100},
{"XC", 90}, {"LXXX", 80}, {"LXX", 70}, {"LX", 60}, {"L", 50}, {"XL", 40}, {"XXX", 30}, {"XX", 20}, {"X", 10},
{"IX", 9}, {"VIII", 8}, {"VII", 7}, {"VI", 6}, {"V", 5}, {"IV", 4}, {"III", 3}, {"II", 2}, {"I", 1}
};
- 方法二：映射表不需要那么大棒旗，只要保存M D C L X V I這七個基本羅馬數(shù)字和阿拉伯數(shù)字的對應(yīng)關(guān)系就可以了：
unordered_map<char, int> s2i{{'M', 1000}, {'D', 500}, {'C', 100}, {'L', 50}, {'X', 10}, {'V', 5}, {'I', 1}};
然后逐字符遍歷字符串喘批，也不需要切割字符串撩荣。判斷當前字符是不是比下一個字符要對應(yīng)的阿拉伯數(shù)字要大，如果大饶深，就加上當前字符對應(yīng)的阿拉伯數(shù)字餐曹；否則減。
要點
- 羅馬數(shù)字最混淆不清的就是CM(900) XL(40) IV(4)這些數(shù)字敌厘，涉及到大位數(shù)字減去小位數(shù)字台猴；
- c++的字符串處理，不得不說俱两，真的很爛饱狂。。宪彩。
時間復雜度
O(n)休讳，n為羅馬數(shù)字長度。實際上這個數(shù)字很短尿孔，3999對應(yīng)的羅馬數(shù)字MMMCMXCIX才9位數(shù)字俊柔，所以時間復雜度幾乎為O(1).
空間復雜度
O(1)
代碼
方法一
class Solution {
public:
int romanToInt(string s) {
vector<pair<string, int>> s2i{{"MMM", 3000}, {"MM", 2000}, {"M", 1000},
{"CM", 900}, {"DCCC", 800}, {"DCC", 700}, {"DC", 600}, {"D", 500}, {"CD", 400}, {"CCC", 300}, {"CC", 200}, {"C", 100},
{"XC", 90}, {"LXXX", 80}, {"LXX", 70}, {"LX", 60}, {"L", 50}, {"XL", 40}, {"XXX", 30}, {"XX", 20}, {"X", 10},
{"IX", 9}, {"VIII", 8}, {"VII", 7}, {"VI", 6}, {"V", 5}, {"IV", 4}, {"III", 3}, {"II", 2}, {"I", 1}
};
int res = 0;
for (size_t i = 0; i < s.size();) {
for (size_t j = 0; j < s2i.size(); j++) {
if (i + s2i[j].first.size() > s.size()) continue;
string roman = s.substr(i, s2i[j].first.size());
if (roman == s2i[j].first) {
res += s2i[j].second;
i += s2i[j].first.size();
break;
}
}
}
return res;
}
};
方法二
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> s2i{{'M', 1000}, {'D', 500}, {'C', 100}, {'L', 50}, {'X', 10}, {'V', 5}, {'I', 1}};
int res = 0;
for (int i = 0; i < s.length() - 1; i++) {
if (s2i[s[i]] < s2i[s[i + 1]])
res -= s2i[s[i]];
else
res += s2i[s[i]];
}
res += s2i[s.back()];
return res;
}
};
