Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title Description

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

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

Character values I 1 V 5 X 10 L 50 C 100 D 500 M 1000Copy the code

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. Given a Roman numeral, convert it to an integer.

 

Example 1:

Input: s = "III" Output: 3Copy the code

Example 2:

Input: s = "IV" Output: 4Copy the code

Example 3:

Input: s = "IX" Output: 9Copy the code

Example 4:

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

Example 5:

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

Tip:

  • 1 <= s.length <= 15
  • S contains only characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
  • The data guarantees that s is a valid Roman numeral and represents an integer within the range [1, 3999]
  • All test cases are in accordance with the Roman numerals writing rules, and there will be no cross-position.
  • Examples like IL and IM don’t fit the question, 49 should be XLIX, 999 should be CMXCIX.
  • For detailed rules for writing Roman numerals, see Roman numerals – Mathematics.

Second, train of thought analysis

The general idea is to take what you need to subtract separately, and add up the rest

Map is used to store the characters and corresponding numeric meanings

Special case: the next digit of example I is V or X

Because we need to process the next bit to avoid exceeding the length of the array, we need to determine if it is the last bit and dispose of it in advance

AC code

class Solution {
    public int romanToInt(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Integer> map = new HashMap(16);
        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);
        int result = 0;
        for (int i = 0; i < chars.length; i++) {
            char temp  = chars[i];
            // If it is already the last digit, add it directly
            if(i == chars.length - 1){
                result += map.get(temp);
                continue;
            }
            // Next character
            char tempNext  = chars[i + 1];
            // Special rules handle subtractions
            if(temp == 'I' && (tempNext == 'V' || tempNext == 'X')){
                result -= map.get(temp);
                continue;
            }
            if(temp == 'X' && (tempNext == 'L' || tempNext == 'C')){
                result -= map.get(temp);
                continue;
            }
            if(temp == 'C' && (tempNext == 'D' || tempNext == 'M')){
                result -= map.get(temp);
                continue;
            }
            // The remainder of the special case
            result += map.get(temp);
        }
        returnresult; }}Copy the code

Four,

The code is a bit long, but the thinking is clear.

Model reference

Roman numeral to integer – Roman numeral to integer – LeetCode (leetcode-cn.com)