LeetCode13.罗马数字转整数（三种解法）

题目描述

罗马数字包含以下七种字符: 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 = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/roman-to-integer

 

方法1： 枚举法，也叫if else暴力破解法

class Solution {
public:
    int romanToInt(string s) {
        int n=s.size();
        int sum=0;
        for(int i=0;i<n;i++){
            if(i+1<n&&s[i]=='I'&&s[i+1]=='V'){
                sum+=4;
                i++;//当前位置和后一个位置的字符构成特殊情况的字符，则直接越过该字符，移动变量加1 
            }else if(i+1<n&&s[i]=='I'&&s[i+1]=='X'){
                sum+=9;
                i++;
            }else if(i+1<n&&s[i]=='X'&&s[i+1]=='L'){
                sum+=40;
                i++;
            }else if(i+1<n&&s[i]=='X'&&s[i+1]=='C'){
                sum+=90;
                i++;
            }else if(i+1<n&&s[i]=='C'&&s[i+1]=='D'){
                sum+=400;
                i++;
            }else if(i+1<n&&s[i]=='C'&&s[i+1]=='M'){
                sum+=900;
                i++;
            }
            else{
                if(s[i] == 'I') sum+=1;
                else if(s[i] == 'V') sum += 5;
                else if(s[i] == 'X') sum += 10;
                else if(s[i] == 'L') sum += 50;
                else if(s[i] == 'C') sum += 100;
                else if(s[i] == 'D') sum += 500;
                else if(s[i] == 'M') sum += 1000;
            }
        } 
    return sum;
    }
};

方法2：巧解法：考虑每个字符对应的值与其后一个字符对应的值的关系，如果小于则该字符对应的值变为负数，否则仍为正数，最后循环累加即可

class Solution{
	public:
        //建立键值表
		int getValue(char a){
			    switch(a){
					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;
				}
            } 
		int romanToInt(string s){
			int n=s.size();
	        int sum=0,i=0;
	        for(i=0;i<n;i++){
 /*使用单目判断运算符，将当前值与后一个值进行比较，如果当前值大于后一个值则当前值
为正，否则就是题目所描述的特殊情况，当前值变为负，进行循环累加各个字符对应的值即可*/
		          sum+=getValue(s[i+1])>getValue(s[i])? -getValue(s[i]):getValue(s[i]);
	        }
	        return sum;
		}
}; 

方法3：逆向思维，从右向左遍历，记录当前的最大值，如果遇到更大的则相加，遇到更小的则相减（这个思路真的很简洁也易懂，一位网友在评论区码的）

class solution{
	public:
		    //建立键值表
		    int getValue(char a){
			switch(a){
					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;
				}
            } 
            //方法三：逆向思维，从右向左遍历，记录当前的最大值，如果遇到更大的则相加，遇到更小的则相减
			int function3(string s){
				int n=s.size();
				int max=1,sum=0,level=0;//level记录当前值
				for(int i=n-1;i>=0;i--){
					level=getValue(s[i]);
					if(level>=max){
						sum+=level;
						max=level;//更新最大值
					}else{
						sum-=level;
					}
				}
				return sum;
			} 
}; 

先从简单题做起，每天坚持刷至少一题，持续分享刷题心得与过程！

点赞加关注，一起享受刷题的乐趣！