13.Roman to Integer (HashTable)

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

class Solution {
public:
int romanToInt(string s) {
char c[] = {'I','V','X','L','C','D','M'};
int n[] = {,,,,,,};
unordered_map<char,int> map;
map.insert(make_pair('I',));
map.insert(make_pair('V',));
map.insert(make_pair('X',));
map.insert(make_pair('L',));
map.insert(make_pair('C',));
map.insert(make_pair('D',));
map.insert(make_pair('M',)); int len = s.length();
int num = ;
if(len==){
num = map[s[]];
return num;
} for(int i = ; i < len; i++){
if(map[s[i]] <= map[s[i-]]){
num += map[s[i-]];
}
else{
num+= map[s[i]]-map[s[i-]];
i++; //dealt two letters at one time, so i should increase 2
}
} //Do not forget to discuss the last case independently
if(len > && map[s[len-]] <= map[s[len-]]){
num+=map[s[len-]];
} return num;
}
};

Improve: 使用两个数组代替map,更节省空间。

class Solution {
public:
int romanToInt(string s) {
int values[] = {, , , , , , };
char numerals[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I' };
int i = , j = , result = ;
while(i < s.length()){
if(s[i] != numerals[j]){
j++;
continue;
} if(i+<s.length() && j->= && s[i+] == numerals[j-]){
result += values[j-]-values[j];
i+=;
}
else if(i+<s.length() && j->= && s[i+] == numerals[j-]){
result += values[j-]-values[j];
i+=;
}
else{
result += values[j];
i++;
}
}
return result;
}
};
上一篇:mmm-master漂移问题的分析


下一篇:Xamarin.Forms学习之Page Navigation(二)