# [leetcode] hash table - Roman numeral to integer

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

characternumerical value
I1
V5
X10
L50
C100
D500
M1000

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 in V (5) and X (10) To the left of the, to represent 4 and 9.
X Can be placed in L (50) and C (100) To the left of the, for 40 and 90.
C Can be placed in D (500) and M (1000) To the left of the, to represent 400 and 900.
Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.

```

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3

Example 5:

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

Tips:

1 <= s.length <= 15
s contains only characters ('I ',' V ',' X ',' L ',' C ','D','M ')
The title data ensures that s is a valid Roman numeral and represents an integer in the range [1, 3999]
The test cases given in the title comply with the Roman numeral writing rules, and there will be no cross position and so on.
Examples such as IL and IM do not meet the title requirements. 49 should write XLIX and 999 should write CMXCIX.
For detailed writing rules of Roman numerals, please refer to Roman numerals - Mathematics.

Idea 1:
Take out the strings one by one
Traversal is compared, and the left and right numbers are compared and traversed in turn
Keep the value of the current bit. When traversing to the next bit, compare the size relationship between the reserved value and the traversal bit, and then determine whether the reserved value is plus or minus. Just add the last one

The specific codes are as follows

The main string functions used to get a single character are charAt()
See my article for details
Detailed analysis of charAt usage in java (full)

```class Solution {
public int romanToInt(String s) {
int sum = 0;
int preNum = getValue(s.charAt(0));
for(int i = 1;i < s.length(); i ++) {
int num = getValue(s.charAt(i));
if(preNum < num) {
sum -= preNum;
} else {
sum += preNum;
}
preNum = num;
}
sum += preNum;
return sum;
}

private int getValue(char ch) {
switch(ch) {
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;
default: return 0;
}
}
}
```

Idea 2:
Through train of thought 1, we can also see that it is actually a replacement of hash table
Replace it with a hash table
For the specific hash table set, please refer to my previous articles
100000 word summary of javaSE from entry to mastery (end)

```class Solution {
Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};

public int romanToInt(String s) {
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int value = symbolValues.get(s.charAt(i));
if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
ans -= value;
} else {
ans += value;
}
}
return ans;
}
}
```

Keywords: Algorithm leetcode

Added by sprint10s on Wed, 13 Oct 2021 05:38:31 +0300