罗马数字转整数

一 问题描述

罗马数字包含七种字符： I ， V ， X ， L ， C ， D ， M 。

例如：罗马数字 2 写做 II ， 12 写做 XII ， 27 写做 XXVII 。

通常情况下罗马数字中小的数字在大的数字右边，但也有特例。如 4 不写做 IIII ，而是 IV ， 9 写做 IX 。这个特殊规则如下：

• I 可以放在 V 和 X 的左边，来表示 4 和 9

• X 可以放在 L 和 C 的左边，来表示 40 和 90

• C 可以放在 D 和 M 的左边，来表示 400 和 900

给定一个表示罗马数字的字符串，将其转换为整数。

13. 罗马数字转整数

二 解决方法

1 模拟

分析

不考虑特殊情况，罗马数字中的七种字符分别代表7个不同数值。也就是说：只要将字符串的每一个字符转换成对应的数值，然后将其累加起来，就可以得到其对应整数。

考虑特殊情况，当位于左边的罗马数字小于其右边的时，左边罗马数字取负。

使用哈希表存储罗马字符与对应数值的映射关系，便于使用。

代码

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> _map = {						// 罗马字符-数值映射表
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000},
        };
        int n = s.size();										// 字符串长度
        int sum = 0;											// 初始化总和为0（返回值）
        for (int i = 0; i < n; ++i) {							// 遍历罗马数字字符串
            int value = _map[s[i]];								// 根据映射表获取当前字符数值
            if (i < n - 1 && value < _map[s[i + 1]]) {			// 考虑特殊情况
                sum -= value;									// 当前数值小于右侧数值，取负值
            } else {
                sum += value;									// 否则取正值
            }
        }
        return sum;												// 返回总和
    }
};

复杂度

• 只遍历长度为 n 的字符串一次，因此时间复杂度为 O(n) 。

• 只使用常量个变量，因此空间复杂度为 O(1) 。

三 总结

• 有些问题只能根据题意模拟它的解决思路，并没有其他巧妙的方法。