Topic describes

This is the conversion of 13 Roman numerals to integers on LeetCode. The difficulty is simple.

Keywords: string, number, hash table, analog

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:

  1. I can be placedV (5) 和 X (10)To the left of theta4 和 9.
  2. X can be placedL (50) 和 C (100)To the left of theta40 和 90.
  3. C can be placedD (500) 和 M (1000)To the left of theta400 和 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: 3Copy the code

Example 2:

Input: "IV" Output: 4Copy the code

Example 3:

Input: "IX" Output: 9Copy the code

Example 4:

Input: "LVIII" Output: 58 Interpretation: L = 50, V= 5, III = 3Copy the code

Example 5:

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

Tip:

  • 1 <= s.length <= 15
  • sOnly contain characters('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • Subject data guaranteesIs a valid Roman numeral and indicates that the integer is in range[1, 3999] 内
  • All test cases are in accordance with the Roman numerals writing rules, and there will be no cross-position.
  • IL 和 IMThat’s not the case,49You should writeXLIX.999You should writeCMXCIX 。

To highlight

  • Usually, the smaller Roman numerals are to the right of the larger numerals
  • The critical situation

Their thinking

In the normal case, the order from largest to smallest is the sum of all characters.

When a small value occurs to the right of a large value, we can think of it as plus a large value minus a small value. So we can maintain a hash table that represents the actual value that each character represents. Iterate through the string and decide that if there is a small value to the left, subtract the small value, add the other case, but be careful about the threshold value, because you want to determine the length of the current character and the next character, so you can’t overstep the bounds.

class Solution {
    public int romanToInt(String s) {
        // Create a Hash table to store the mapping
        HashMap<Character, Integer> map = new HashMap<>(7);
        map.put('I'.1);
        map.put('V'.5);
        map.put('X'.10);
        map.put('L'.50);
        map.put('C'.100);
        map.put('D'.500);
        map.put('M'.1000);

        // Start iterating over the string
        char[] cs = s.toCharArray();
        int len = s.length();
        int ans = 0;
        for (int i = 0; i < len; i++) {
            int value = map.get(cs[i]);
            // Is not the last character and the minor value is on the left. subtracting
            if (i < len-1 && value < map.get(cs[i+1])) {
                ans -= value;
            } else{ ans += value; }}returnans; }}Copy the code

reference

My Github repository has been set up synchronously, click access