13. Roman to Integer

二刷 08/2022

Version #1 HashMap

Time O(L)

Space O(1)

Runtime: 13 ms, faster than 32.06% of Java online submissions for Roman to Integer.

Memory Usage: 46.8 MB, less than 29.88% of Java online submissions for Roman to Integer.

class Solution {

    public int romanToInt(String s) {

        int result = 0;

        Map<Character, Integer> map = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);

        Integer next = null;

        for (int i = s.length() - 1; i >= 0; i--) {

            int val = map.get(s.charAt(i));

            if (next != null && next > val) {

                result -= val;

            } else {

                result += val;

            }

            next = val;

        }

        return result;

    }

}

一刷

"A number in Roman Numerals is a string of these symbols written in descending order(e.g. M’s first, followed by D’s, etc.). However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX), subtractive notation is often used"

"

1. Split the Roman Numeral string into Roman Symbols (character).
2. Convert each symbol of Roman Numerals into the value it represents.
3. Take symbol one by one from starting from index 0:
   • If current value of symbol is greater than or equal to the value of next symbol, then add this value to the running total.
   • else subtract this value by adding the value of next symbol to the running total."

45.03 %

class Solution {
    public int romanToInt(String s) {
        if (s == null) return 0;
        Map<Character, Integer> map = new HashMap<>();
        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;
        int prev = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int curr = map.get(s.charAt(i));
            if (curr > prev) {
                result -= 2 * prev;
            }
            result += curr;
            prev = curr;
        }
        return result;
    }
}