Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Convert Roman numerals entered into integers.”

Title link: Source: LeetCode

Link: 13. Roman numerals to integers – LeetCode (leetcode-cn.com)

2

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

character The numerical
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 ones side by side. Write XII as X + II. Write XXVII as XX + V + II.

Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it’s written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six situations:

I can be put 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 put to the left of D (500) and M (1000) to represent 400 and 900.

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

Example 1: Input: num = "III" Output: 3Copy the code
Example 2: Input: num = "XLVIII" Output: 48 Resolution: XL = 40, V = 5, III = 3Copy the code
Example 3: Input: num = "MIVCMXCIV" Output: 4994 Resolution: MIV = 4000, CM = 900, XC = 90, IV = 4Copy the code

Second, the problem solving

1. Analysis of ideas

Roman numerals are converted to integers in two main cases:

  • One is that the larger digit comes first and the smaller digit comes later, which converts each character into a value and adds it up. Such as VI = 5 + 1 = 6
  • One is the case where the small number is in front of the large number, and the small number needs to be subtracted according to the rules. In this way, each character can be converted into a value. If the number to the right of the number is larger than itself, the number sign is reversed. For example XIV = X-i + V = 10-1 + 5 = 14

2. Code implementation

Simulation:

According to the idea of solving the problem, the input Roman numerals are compared in turn and divided into two cases for calculation:

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; }}returnans; }}Copy the code

Substitution string

This is an interesting solution, using C#’s string substitution method, replace two special characters into a character, and then the character into the corresponding unique number, add can be.

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; }}returnsum; }}Copy the code

3. Time complexity

Time complexity: O(n)

Where n is the length of the string s.

Space complexity: O(1)

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

Third, summary

This problem sets up a dictionary to record all the substrings of Roman numerals, and then divides them into two cases based on whether the large number comes first or the small number comes first, and then analyzes each case differently.

When you solve a problem, you have to take all of these things into account, otherwise you’re going to get a slightly different result.