1, Simple question 13 Roman numeral to integer

1.1 Title Description

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

character          numerical 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 two parallel ones. 12 is written as XII, which is X + II. 27 write 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 in the number 5
To the left of, the number represented is equal to the large number 5 minus the decimal number 1 to get the value 4. 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.

1.2 problem solving ideas

Judging from left to right, if any special combination (i.e. beginning with 4 / 9) is met, the two characters will be considered together, answer+=4/9/40/90..., indicator index+=2
Otherwise, answer+=1/5/10/50..., indicator index+=1
(this method is not very good because it needs to write more judgments)

Next, consider judging from right to left. It can be seen from the observation that each special combination indicates that the character of small number is on the left of large character. Therefore, if there is a small character on the left, subtract the small character from the original basis - IV=5-1.
Through logic, record the current maximum characters from right to left. If smaller characters are encountered, subtract the value, otherwise add the value and update the maximum value.

Right to left diagram:

From right to left:

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 answer=0;
        int curIndex=s.length()-1;
        int curMax=symbolValues.get(s.charAt(curIndex));
        while(curIndex>=0){
            int mid=symbolValues.get(s.charAt(curIndex));
            if(mid>=curMax){
                curMax=mid;
                answer+=mid;
            }
            else
                answer-=mid;
            curIndex--;
        }
        return answer;
    }
}

2, Medium question 12 Integer to Roman numeral

2.1 Title Description

Convert no more than 3999 numbers into Roman numbers. The rules are the same as above (the idea of solving the problem is a little around, but it feels simpler)

2.2 problem solving ideas

Hard coded problem solving - since there are few possibilities, give each possibility a corresponding code

class Solution {
    String[] thousands= {"", "M", "MM", "MMM"};
    String[] hundreds= {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String[] tens= {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String[] ones= {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }
}

Greedy - because of the transformation rules (there are larger Roman numerals, represented by larger Roman numerals), each possibility is given and judged from large to small.

class Solution {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }
}

ending

Source: LeetCode link: https://leetcode-cn.com/problems

Pay attention to the author, take you to brush the questions every day, and learn the most commonly used algorithm skills from simple algorithm problems (algorithm problem solving every two days and one shift)
Two algorithm problems of the same type every day - simple to advanced, let you unknowingly become a ruthless problem brushing machine