[clock out algorithm] 13. Analysis of Roman numeral to integer algorithm

1, Title

1. Algorithm topic

Convert the entered Roman numerals to integers

Title Link:
Source: LeetCode

Link: 13. Roman numeral to integer LeetCode (LeetCode CN. Com)

2. Title Description

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

character	numerical value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, the Roman numeral 2 is written as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.

Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:

I can be placed to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be placed to the left of D (500) and M (1000) to represent 400 and 900.

Give you a Roman number and turn it into an integer. Make sure the input is in the range of 1 to 3999.

Example 1:
Input: num = "III"
Output: 3

Example 2:
Input: num = "XLVIII"
Output: 48
 analysis: XL = 40 , V = 5 , III = 3

Example 3:
Input: num = "MIVCMXCIV"
Output: 4994
 Resolution: MIV = 4000 , CM = 900 , XC = 90 , IV = 4

2, Problem solving

1. Train of thought analysis

Roman numerals to integers are mainly divided into two cases:

One is that large numbers come first and small numbers come later. This can convert each character into a value and accumulate it. For example, VI=5+1=6
One is when the small number is in front of the large number. You need to subtract the small number according to the rules. In this way, each character can be converted into a value. If the number on the right of the number is larger than itself, the number symbol will be reversed. For example, XIV = X - I + V =10 - 1 + 5 = 14

2. Code implementation

Simulation method:

According to the problem-solving idea, the input Roman numerals are compared in turn and calculated in two cases:

public class Solution 
{
    public int RomanToInt(string s) 
    {
            Dictionary<char, int> Values = new Dictionary<char, int> { { 'I', 1 }, { 'V', 5 }, { 'X', 10 }, { 'L', 50 }, { 'C', 100 }, { 'D', 500 }, { 'M', 1000 } };
            int ans = 0;
            int n = s.Length;
            for (int i = 0; i < n; ++i)
            {
                int value = Values[s[i]];
                if (i < n - 1 && value < Values[s[i + 1]])
                {
                    ans -= value;
                }
                else
                {
                    ans += value;
                }
            }
            return ans;
    }
}

Replace string

This is an interesting solution. Using the string replacement method of C#, two special characters are replaced with one character, and then the character is transformed into the corresponding unique number for addition.

public class Solution 
{
    public int RomanToInt(string s) 
    {
        s = s.Replace("IV","Y");
        s = s.Replace("IX","T");
        s = s.Replace("XL","U");
        s = s.Replace("XC","R");
        s = s.Replace("CD","O");
        s = s.Replace("CM","W");
        int sum = 0;
        int i = 0;
        for (i = 0; i < s.Length; i++)
        {
            switch (s[i])
            {
                case 'M':
                    sum += 1000;
                    break;
                case 'W':
                    sum += 900;
                    break;
                case 'D':
                    sum += 500;
                    break;
                case 'O':
                    sum += 400;
                    break;    
                case 'C':
                    sum += 100;
                    break;
                case 'R':
                    sum += 90;
                    break;
                case 'L':
                    sum += 50;
                    break;
                case 'U':
                    sum += 40;
                    break;
                case 'X':
                    sum += 10;
                    break;
                case 'T':
                    sum += 9;
                    break;
                case 'V':
                    sum += 5;
                    break;
                case 'Y':
                    sum += 4;
                    break;
                case 'I':
                    sum += 1;
                    break;
            }
        }
        return sum;
    }
}

3. Time complexity

Time complexity: O(n)

Where n is the length of the string s.

Space complexity: O(1)

The amount of calculation is independent of the size of the input number.

3, Summary

This problem is to build a dictionary to record all Roman numeral substrings, and then divide them into two cases according to whether large numbers come first or small numbers come first, and then analyze them differently in different cases.

When solving problems, we need to take all the situations into account, otherwise the results of transformation will be different.

Keywords: Algorithm

Added by cwarn23 on Mon, 25 Oct 2021 08:13:34 +0300

Programming VIP