[LeetCode] 13. Roman to Integer

Medium
Related Topics: Hash Table / Math / String
LeetCode Source

解题想法

LeetCode Hint: Problem is simpler to solve by working the string from back to front and using a map.

首先，我们先建立一个 Hash Table mp

在过程中，我们透过比较当前 mp[s[i]] 的值跟前面遍历值 prev_val 之大小

不过重点是最后每遍历一个值要储存 prev_val = mp[s[i]]

Python

class Solution:    def romanToInt(self, s: str) -> int:        mp = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}        res = 0        prev_value = 0  # To keep track of the value of the previous Roman numeral        for i in range(len(s) - 1, -1, -1):            if mp[s[i]] < prev_value:                res -= mp[s[i]]            else:                res += mp[s[i]]            prev_value = mp[s[i]]        return res

C++

class Solution {public:    int romanToInt(string s) {        unordered_map <char, int> mp = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};        int res = 0, prev_val = 0;        for (int i = s.size()-1; i > -1; i--) {            if (mp[s[i]] < prev_val)                res -= mp[s[i]];            else                res += mp[s[i]];            prev_val = mp[s[i]];        }        return res;    }};

这系列文被记录在 Top Interview 150 Series