Mind palace

some thoughts

0%

13. Roman to Integer

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(n)
一般罗马数字都是从大到小排列，如果发现当前数字小于下一个，如IV，则减去当前数字，即-1 + 5 = 4

1
2
3
4
5
6
7
8
9
10
d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            if i > 0 and d[s[i - 1]] < d[s[i]]:
                res -= d[s[i - 1]] * 2
            res += d[s[i]]
        return res
1
2
3
4
5
6
7
8
9
10
11
d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        res, n = 0, len(s)
        for i in range(n):
            if i + 1 < n and d[s[i]] < d[s[i + 1]]:
                res -= d[s[i]]
            else:
                res += d[s[i]]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
unordered_map<char, int> m = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
};
class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (i + 1 < n && m[s[i]] < m[s[i + 1]]) {
                res -= m[s[i]];
            } else {
                res += m[s[i]];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
unordered_map<char, int> m = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
};
class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && m[s[i]] > m[s[i - 1]]) {
                res -= m[s[i - 1]] * 2;
            }
            res += m[s[i]];
        }
        return res;
    }
};