Li Kou daily question - day 31 -13 Roman array to integer

2022.6.29 Did you brush the questions today ？

---

subject ：

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 .

analysis ：
Give you a string , You need to convert it into numbers according to Roman rules , What needs to be noted is

The front number Less than Back , Make a difference

Front array Greater than Back , Then do and

Ideas ： We insert the relationship between strings and numbers into the hash table , Then iterate through the string , Judge according to the mapping relationship of hash table , Store the value in vector in , Right again vector Make a judgment and get the result

analysis ：

1. Hash table solving

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int>map;
        vector<int>vec;
        int res = 0;
        map['I'] = 1;
        map['V'] = 5;
        map['X'] = 10;
        map['L'] = 50;
        map['C'] = 100;
        map['D'] = 500;
        map['M'] = 1000;
        for (auto& c : s)
        {
            vec.push_back(map[c]);
        }
        for (auto i = 0; i < vec.size();i++ )
        {
            if (i < vec.size() - 1 && vec[i] < vec[i + 1])
            {
                res -= vec[i];
            }
            else
            {
                res += vec[i];
            }
            
        }
        return res;
    }
};

2. Hash table optimization

We can vector Omit , Directly use the mapping relationship to make judgments

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int>map;

        int res = 0;
        map['I'] = 1;
        map['V'] = 5;
        map['X'] = 10;
        map['L'] = 50;
        map['C'] = 100;
        map['D'] = 500;
        map['M'] = 1000;
        for (auto i = 0; i < s.size(); i++)
        {
            if (i < s.size() - 1 && map[s[i]] < map[s[i+1]])
            {
                res -= map[s[i]];
            }
            else
            {
                res += map[s[i]];
            }

        }
        return res;
    }
};