Leetcode13. Roman numeral to integer (three solutions)

Title Description

Roman numerals contain the following seven characters : I, V, X, L,C,D  and  M.

character           The number
I                 1
V               5
X              10
L               50
C              100
D              500
M             1000

for example , Rome digital 2 Write to do  II , Two parallel 1 .12 Write to do  XII , That is to say  X + II . 27 Write to do   XXVII, That is to say  XX + V + II .

Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write  IIII, It is  IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as  IX. This special rule only applies to the following six cases ：

I  Can be placed in  V (5) and  X (10) Left side , To express 4 and 9.
X  Can be placed in  L (50) and  C (100) Left side , To express 40 and  90. 
C  Can be placed in  D (500) and  M (1000) Left side , To express  400 and  900.
Given a Roman number , Convert it to an integer .

Example 1：

 Input : s = "III"
 Output : 3

Example 2：

 Input : s = "MCMXCIV"
 Output : 1994
 explain : M = 1000, CM = 900, XC = 90, IV = 4

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/roman-to-integer

 

Method 1：  Enumeration , Also called if else brute-force attack

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++;// Characters in the current position and the next position constitute characters in special cases , Then directly cross the character , Move variable plus 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;
    }
};

Method 2： Ingenious solution ： Consider the relationship between the value corresponding to each character and the value corresponding to the next character , If less than, the value corresponding to this character becomes negative , Otherwise, it is still positive , Finally, cycle and accumulate

class Solution{
	public:
        // Create a key value table 
		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++){
 /* Use the monocular judgment operator , Compare the current value with the next value , If the current value is greater than the latter value, the current value 
 Being positive , Otherwise, it is the special situation described in the title , The current value becomes negative , Cycle and accumulate the corresponding values of each character */
		          sum+=getValue(s[i+1])>getValue(s[i])? -getValue(s[i]):getValue(s[i]);
	        }
	        return sum;
		}
}; 

Method 3： Converse thinking , Traverse from right to left , Record the current maximum , If you encounter larger ones, add them , Meet smaller ones and subtract （ This idea is really simple and easy to understand , A netizen commented on the area code ）

class solution{
	public:
		    // Create a key value table 
		    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;
				}
            } 
            // Method 3 ： Converse thinking , Traverse from right to left , Record the current maximum , If you encounter larger ones, add them , Meet smaller ones and subtract 
			int function3(string s){
				int n=s.size();
				int max=1,sum=0,level=0;//level Record the current value 
				for(int i=n-1;i>=0;i--){
					level=getValue(s[i]);
					if(level>=max){
						sum+=level;
						max=level;// Update Max 
					}else{
						sum-=level;
					}
				}
				return sum;
			} 
}; 

Start with simple questions , Brush at least one question every day , Continue to share the experience and process of topic brushing ！

Pay attention to , Enjoy the fun of writing questions together ！