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

Source: LeetCode

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

Character value 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 the parallel 1. 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.
  • IL 和 IM49. What is the meaning of the passageXLIX999 should writeCMXCIX 。
  • For detailed rules for writing Roman numerals, see Roman numerals – Mathematics.

Second, train of thought analysis

All combinatorial possibilities are first listed and added to the hash table

Then the string is traversed, because there are only two combinations, one is 1 character, the other is 2 characters, where 2 characters take precedence over 1 character

Determine whether the combination of two characters exists in the hash table. If it does, the value is fetched and added to the result ANS, and moved back by 2 characters. If it does not exist, it will judge whether the current 1 character exists. If it does, the value will be taken out and added to the result ANS, and the result ANS will be returned after the end of the traversal by 1 character

Three, code implementation

class Solution {
    public int romanToInt(String s) {
        Map<String, Integer> map = new HashMap<>();
        map.put("I".1);
        map.put("IV".4);
        map.put("V".5);
        map.put("IX".9);
        map.put("X".10);
        map.put("XL".40);
        map.put("L".50);
        map.put("XC".90);
        map.put("C".100);
        map.put("CD".400);
        map.put("D".500);
        map.put("CM".900);
        map.put("M".1000);

        int ans = 0;
        for(int i = 0; i < s.length();) {if(i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) {
                ans += map.get(s.substring(i, i+2));
                i += 2;
            } else {
                ans += map.get(s.substring(i, i+1)); i ++; }}returnans; }}Copy the code

4. Operation results

conclusion

The violent solution is to use more speed and space, see others say using switch instead of map faster, to be verified