13. Roman to Integer - Easy

前往題目

想法

• 各種條件就可以判斷
• 可以用Map，但好像沒必要

思路

看了Neetcode大大的影片，恍然大悟，IV，IX這種都是減掉第一個的數值再加上第二個的數值。例如IV是$-1 + 5 = 4$，IX是$-1 + 10 = 9$

而且還有個重點是and條件判斷的時候第一個不符合就不會再判斷第二個了所以可以用在第一個條件判斷是否第二個字在範圍內，然後就可以不用擔心會出界

1. 建立Map
2. 兩兩一組的看，如果是左小右大的話那就是組合，減掉第一個字的數值
3. 不是的話加上就好了

Code (WA)

嘗試用條件，但最後一個小bug是兩兩一組最後有可能會落單，如果沒有IV，IX，XL這種組合的話

以下摺疊為Wrong Answer

▶

class Solution {
    public int romanToInt(String s) {
        int res = 0;

        // Loop pairs
        for (int i = 0; i < s.length() - 1; ++i) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            String combine = s.substring(i, i + 2);

            switch(combine) {
                case "IV":
                    res += 4;
                    ++i;
                    break;
                case "IX":
                    res += 9;
                    ++i;
                    break;
                case "XL":
                    res += 40;
                    ++i;
                    break;
                case "XC":
                    res += 90;
                    ++i;
                    break;
                case "CD":
                    res += 400;
                    ++i;
                    break;
                case "CM":
                    res += 900;
                    ++i;
                    break;
                default:
                    switch(a) {
                        case 'I':
                            res++;
                            break;
                        case 'V':
                            res += 5;
                            break;
                        case 'X':
                            res += 10;
                            break;
                        case 'L':
                            res += 50;
                            break;
                        case 'C':
                            res += 100;
                            break;
                        case 'D':
                            res += 500;
                            break;
                        case 'M':
                            res += 1000;
                            break;
                    }
            }


        }
        return res;
    }
}

Code

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>(Map.of(
                'I', 1,
                'V', 5,
                'X', 10,
                'L', 50,
                'C', 100,
                'D', 500,
                'M', 1000
        ));

        int res = 0;

        for (int i = 0; i < s.length(); ++i) {
            // Check in bound and reverse order
            if (i + 1 < s.length() && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                res -= map.get(s.charAt(i));
            } else {
                res += map.get(s.charAt(i));
            }
        }

        return res;
    }
}

2024/04/17

• 嘗試用雙指針兩兩一組來看，原來不需要
• 每組都判斷就能把IV、IX這種減法的先減去，換到下一組的時候就可以把數字加回來，這樣就剛好完成減法