This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Roman numerals contain the following seven characters: I, V, X, L, C, D and M. Character value I1
V             5
X             10
L             50
C             100
D             500
M             1000For example, Roman numerals2Write it as II, that is, two parallel1 。12Write XII as X + II.27Write XXVII, which is XX + V + II. Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example4I don't write IIII, I write IV. digital1In the digital5To the left of, is equal to the large number5Reduce the number of1The resulting value4. Again, numbers9This is IX. This particular rule applies only to the following six cases: I can be placed in V (5) and X (10) to the left of4 和 9. X can be placed in L (50) and C (100) to the left of40 和 90. C can be placed in D (500) and M (1000) to the left of400 和 900. Given a Roman numeral, convert it to an integer. The sample1: Enter: s ="III"Output:3The sample2: Enter: s ="IV"Output:4The sample3: Enter: s ="IX"Output:9The sample4: Enter: s ="LVIII"Output:58Explanation: L =50, V= 5, III = 3.The sample5: Enter: s ="MCMXCIV"Output:1994Explanation: M =1000, CM = 900, XC = 90, IV = 4.Tip:1 <= s.length <= 15S contains only characters ('I'.'V'.'X'.'L'.'C'.'D'.'M'S is a valid Roman numeral and represents an integer in the range [1.3999] all test cases are in accordance with the Roman numerals writing rules, and there is no cross-position. Examples like IL and IM don't fit the question,49I should write XLIX,999I should write CMXCIX. For detailed rules for writing Roman numerals, see Roman numerals - Mathematics. Source: LeetCode//leetcode-cn.com/problems/roman-to-integerCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. The simulation

Knowing the Corresponding Roman numerals and the formula for calculating them, it is easy to think of replacing Roman numerals with Arabic numerals and then calculating them according to the formula

Here I directly replaced numbers by traversal and switch. I found in the comments section that the same function can be achieved by hashing (Roman numerals as key and corresponding Arabic numerals as value in map, which requires get), but it is said that map takes a little longer time

public int romanToInt(String s) {
    int[] arr = new int[s.length()];
    for (int i = 0; i < s.toCharArray().length; i++) {
        String temp = String.valueOf(s.charAt(i));
        switch (temp) {
            case "I":
                arr[i] = 1;
                break;
            case "V":
                arr[i] = 5;
                break;
            case "X":
                arr[i] = 10;
                break;
            case "L":
                arr[i] = 50;
                break;
            case "C":
                arr[i] = 100;
                break;
            case "D":
                arr[i] = 500;
                break;
            case "M":
                arr[i] = 1000;
                break; }}int res = arr[arr.length - 1];
    for (int i = arr.length - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            res -= arr[i];
        } else{ res += arr[i]; }}return res;
}
Copy the code

2. List all possibilities

The reason why we can’t directly add Roman numerals to Arabic numerals is because two Roman numerals together could either be added or subtracted

But most of them add, very few of them subtract, so find the subtraction and replace it with the corresponding Arabic numerals

This way is very Nice

public int romanToInt2(String s) {
    s = s.replace("IV"."a");
    s = s.replace("IX"."b");
    s = s.replace("XL"."c");
    s = s.replace("XC"."d");
    s = s.replace("CD"."e");
    s = s.replace("CM"."f");

    int result = 0;
    for (int i=0; i<s.length(); i++) {
        result += which(s.charAt(i));
    }
    return result;
}

public int which(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;
        case 'a': return 4;
        case 'b': return 9;
        case 'c': return 40;
        case 'd': return 90;
        case 'e': return 400;
        case 'f': return 900;
    }
    return 0;
}
Copy the code

In fact, it is not much faster than the first way, and more memory