【题目描述】
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
【测试用例】
示例1：
输入：s="III"
输出：3
示例2：
输入：s="IV"
输出：4
示例3：
输入：s="IX"
输出：9
示例4：
输入：s="LVIII"
输出：58
解释：L=50，V=5，III=3
示例5：
输入：s="MCMXCIV"
输出：1994
解释：M=1000，CM=900，XC=90，IV=4
【思路分析】
我的解法很简单也很暴力，用sum存储结果，一个for循环依次遍历字符串，'I'，'X'，'C'三个字符做特殊处理（对应罗马数字的六种特殊情况）：
如果当前字符是'I'，看下一个字符是不是'V'或者'X'，是'V'的话sum+=4，是'X'的话sum+=9；
如果当前字符是'X'，看下一个字符是不是'L'或者'C'，是'L'的话sum+=40，是'C'的话sum+=90；
如果当前字符是'C'，看下一个字符是不是'D'或者'M'，是'D'的话sum+=400，是'M'的话sum+=900；
其余情况按照罗马数字与整数的对应值直接加到sum就好。
【参考代码】
C和C++实现核心逻辑是一样的，不同的只是语法差异，之所以写两种只是为了练习两种语言的语法而已。
C语言实现
#include <stdio.h>
#include <string.h>
//easy-13-罗马数字转整数
int romanToInt(char* s);
int charToInt(char c);
int main(){
char s[15];
scanf("%s", s);
int res = romanToInt(s);
printf("%d\n", res);
return 0;
}
int romanToInt(char* s){
int i,sum=0;
for(i=0;i<strlen(s);i++){
if(s[i]=='I'){
if(s[i+1]=='V'){
sum+=4;
i++;
}else if(s[i+1]=='X'){
sum+=9;
i++;
}else{
sum+=1;
}
}else if(s[i]=='X'){
if(s[i+1]=='L'){
sum+=40;
i++;
}else if(s[i+1]=='C'){
sum+=90;
i++;
}else{
sum+=10;
}
}else if(s[i]=='C'){
if(s[i+1]=='D'){
sum+=400;
i++;
}else if(s[i+1]=='M'){
sum+=900;
i++;
}else{
sum+=100;
}
}else{
sum = sum + charToInt(s[i]);
}
}
return sum;
}
int charToInt(char c){
switch(c){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
}
return 0;
}C++实现
#include <iostream>
#include <string>
using namespace std;
//easy-13-罗马数字转整数
class Solution {
public:
int romanToInt(string s);
int charToInt(char c);
};
int Solution::romanToInt(string s){
int i,sum=0;
for(i=0;i<s.length();i++){
if(s[i]=='I'){
if(s[i+1]=='V'){
sum+=4;
i++;
}else if(s[i+1]=='X'){
sum+=9;
i++;
}else{
sum+=1;
}
}else if(s[i]=='X'){
if(s[i+1]=='L'){
sum+=40;
i++;
}else if(s[i+1]=='C'){
sum+=90;
i++;
}else{
sum+=10;
}
}else if(s[i]=='C'){
if(s[i+1]=='D'){
sum+=400;
i++;
}else if(s[i+1]=='M'){
sum+=900;
i++;
}else{
sum+=100;
}
}else{
sum = sum + charToInt(s[i]);
}
}
return sum;
}
int Solution::charToInt(char c){
switch(c){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
}
return 0;
}
int main(){
Solution sol;
string str;
cin>>str;
int res = sol.romanToInt(str);
cout<<res<<endl;
return 0;
}【题解思路】
我每写完一道题都会去看评论大神们的题解，受益匪浅。本题还可以使用哈希法。
在观察罗马数字的规律之后可以发现，一般情况下，罗马数字中任意两个数中左边的数大于等于右边的数，例如："LVIII"，L>V>I；而在六种特殊情况中，左边的数小于右边的数，例如："MCMXCIV"，其中"CM"和"XC"是特殊情况，CM=1000-100=900，也可以理解为-100+1000，"XC"也是同样的道理。
按照上述说法，核心逻辑就可以归纳为：当当前罗马数字小于下一个罗马数字时，减去当前罗马数字对应的整数值，反之则加上当前罗马数字对应的整数值。
使用哈希的方法来存储 {罗马数字:整数值}，在C++中用map容器实现。
我的暴力方法和题解的方法对时空复杂度的影响不是很大，但是题解的方法提供了一种思路：类似于这种两个值一一对应的情况都可以考虑哈希。
【参考代码】
#include <iostream>
#include <string>
#include <map>
using namespace std;
//easy-13-罗马数字转整数
class Solution {
public:
int romanToInt(string s);
};
int Solution::romanToInt(string s){
int res=0;
map<char,int> map_roman={
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D',500},
{'M',1000}
};
int i;
for(i=0;i<s.length();i++){
if(map_roman[s[i]] < map_roman[s[i+1]]){
res -= map_roman[s[i]];
}else{
res += map_roman[s[i]];
}
}
return res;
}
int main(){
Solution sol;
string str;
cin>>str;
int res = sol.romanToInt(str);
cout<<res<<endl;
return 0;
}