更新时间:2022-08-12 18:48:29
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
这是一种首先会想到的思路:一个一个字母解析,先解析是不是双字母罗马数字,如果不是就按单字母罗马数字解析。
/********************************* * 日期:2015-01-22 * 作者:SJF0115 * 题目: 13.Roman to Integer * 网址:https://oj.leetcode.com/problems/roman-to-integer/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> using namespace std; class Solution { public: int romanToInt(string s) { int result = 0; int len = s.length(); if(len <= 0){ return result; }//if for(int i = 0;i < len;++i){ if(s[i] == 'M'){ result += 1000; }//if else if(s[i] == 'D'){ result += 500; } else if(s[i] == 'C'){ if(s[i+1] == 'M'){ result += 900; ++i; }//if else if(s[i+1] == 'D'){ result += 400; ++i; } else{ result += 100; } } else if(s[i] == 'L'){ result += 50; } else if(s[i] == 'X'){ if(s[i+1] == 'C'){ result += 90; ++i; }//if else if(s[i+1] == 'L'){ result += 40; ++i; } else{ result += 10; } } else if(s[i] == 'V'){ result += 5; } else if(s[i] == 'I'){ if(s[i+1] == 'X'){ result += 9; ++i; } else if(s[i+1] == 'V'){ result += 4; ++i; } else{ result += 1; } } }//for return result; } }; int main(){ Solution solution; string roman = "XCVIII"; int result = solution.romanToInt(roman); // 输出 cout<<result<<endl; return 0; }
在一个较大的罗马数字的右边记上一个较小的罗马数字,表示大数字加小数字。在一个较大的数字的左边记上1个较小的罗马数字,表示大数字减小数字。
可以通过判断相邻两个数的大小来计算
class Solution { public: int romanToInt(string s) { int result = 0; int len = s.length(); if(len <= 0){ return result; }//if int value[] = {1000,500,100,50,10,5,1}; // 转换 int i; for(i = 0;i < len-1;++i){ int index = FindIndex(s[i]); int index2 = FindIndex(s[i+1]); // 相邻左边下标大于等于右边下标 if(index <= index2){ result += value[index]; } // 相邻左边下标小于右边下标 else{ result += value[index2] - value[index]; ++i; } }//for if(i != len){ // 最后一个元素 int index = FindIndex(s[len-1]); result += value[index]; }//if return result; } private: int FindIndex(char r){ char roman[] = {'M','D','C','L','X','V','I'}; for(int i = 0;i < 7;++i){ if(r == roman[i]){ return i; }//if }//for return -1; } };
从前向后扫描,如果当前比前一个大,说明这一段的值为当前值减去上一个值(如IV = 5 -1 = 4),否则将当前值加入结果中。
有一点需要说明一下:
假如遍历到CD,遍历‘C’时,‘C’的值小于'D'的值,加入结果中,遍历‘D’时,比前一个值大,结果应该是加上当前值减去上一个值,可是再遍历‘C’时,多加了一个'C'的值
因此在遍历‘D’时应再减去一个‘C’的值。即当前值减去两个上一个值,result += map(s[i]) - 2*map(s[i-1]);
class Solution { public: int romanToInt(string s) { int result = 0; int len = s.length(); // 转换 for(int i = 0;i < len;++i){ if(i > 0 && map(s[i]) > map(s[i-1])){ result += map(s[i]) - 2*map(s[i-1]); } else{ result += map(s[i]); } }//for return result; } private: int map(char r){ switch(r){ case 'M':return 1000; case 'D':return 500; case 'C':return 100; case 'L':return 50; case 'X':return 10; case 'V':return 5; case 'I':return 1; default:return 0; } } };
/*----------------------------------------------------------- * 日期:2015-08-30 * 作者:SJF0115 * 题目: 13.Roman to Integer * 网址:https://oj.leetcode.com/problems/roman-to-integer/ * 结果:AC * 来源:LeetCode -------------------------------------------------------------*/ #include <iostream> #include <vector> using namespace std; class Solution { public: int romanToInt(string s) { int result = 0; int size = s.size(); if(size <= 0){ return result; }//if for(int i = 0;i < size;++i){ if(i == size-1){ result += ValueOfRoman(s[i]); }//if else{ int a = ValueOfRoman(s[i]); int b = ValueOfRoman(s[i+1]); if(a < b){ result -= a; }//if else{ result += a; }//else }//else }//for return result; } private: int ValueOfRoman(char roman){ switch(roman){ case 'M': return 1000; case 'D': return 500; case 'C': return 100; case 'L': return 50; case 'X': return 10; case 'V': return 5; case 'I': return 1; default: return 0; } } }; int main(){ Solution solution; string roman = "XCIII"; int result = solution.romanToInt(roman); // 输出 cout<<result<<endl; return 0; }