力扣面试150 罗马数字转整数 预处理 找规律 一题双解

Problem: 13. 罗马数字转整数

思路

👨‍🏫 参考题解
一言蔽之，把一个小值放在大值的左边，就是做减法，否则为加法。

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(1)$

💖 找规律

class Solution {
    public int romanToInt(String s) {
        int n = s.length();
        int res = 0;
        int x = getValue(s.charAt(0));
        for(int i = 1;i < n; i++)
        {
            int y = getValue(s.charAt(i));
            if(x < y)
            {
                res -= x;
            }
            else
            {
                res += x;
            }
            x = y;
        }
        res += x;
        return res;
    }

        private int getValue(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;
            default: return 0;
        }
    
        }
}

💖 预处理

class Solution {
    public int romanToInt(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;
    }
}