13. Roman to Integer

https://leetcode.com/problems/roman-to-integer/description/

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Thoughts

罗马数字转成整形。转换规则是遇到M, D, C, L, X, V和I分别加1000, 500, 100, 50, 10, 5, 1. str中如果有 IV, IX, XL, XC,CD和CM再分别减去2, 2, 20, 20, 200和200。除了按照以上规则hard code外还可以倒着处理，当遇到值比下一位低的做减法，否则加。

参考了这。

Code

/*
 * @lc app=leetcode id=13 lang=cpp
 *
 * [13] Roman to Integer
 */

// @lc code=start
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> m = { { 'I' , 1 },
                                   { 'V' , 5 },
                                   { 'X' , 10 },
                                   { 'L' , 50 },
                                   { 'C' , 100 },
                                   { 'D' , 500 },
                                   { 'M' , 1000 } };
       int res = 0;
       for (int i = s.length() - 1; i >= 0; --i) {
           if (i < s.length() - 1 && m[s[i]] < m[s[i + 1]]) res -= m[s[i]];
           else res += m[s[i]];
       }
       return res;
    }
};
// @lc code=end

Analysis

时间复杂度O(N).