题目
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。示例 1:
输入: "III"
输出: 3示例 2:
输入: "IV"
输出: 4示例 3:
输入: "IX"
输出: 9示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
思考
这个题，我一上来想到的就是最直观的解法，把所有可能的组合字符找出来，例如“IV”，“XL”，“CM”之类的，然后去跟得到的字符串比较，有组合字符的先把组合字符的值求出来，在求单个字符的值。评论里解法里都有很多非常好的类似算法。不过在思考的过程中，我发现凡是需要组合显示的字符都可以这么来理解，就是右边的那个字符需要减去左边的那个字符的值。所以我有个更好的想法大概如下。
解题思路
- 建立基本字符字典，不需要组合字符
- 将得到的字符串倒序后，重新排列，例如“IXLV”->“VLXI”
- 然后对照字典把每个字符的值找出来，放进数组中
- 遍历数值数组，凡是靠后面的数值比前面的数值小的话，将那个数值变为负数
- 然后将数组所有元素相加
Python实现
class Solution: def romanToInt(self, s: str) -> int: #1 d = {'I' : 1, 'V' : 5,'X' : 10,'L' : 50,'C' : 100,'D' : 500,'M' : 1000} #2,3 newNumList = [d[x] for x in s[::-1]] maxNum = 0 index = 0 #4 for i in newNumList: if maxNum < i: maxNum = i if newNumList[index] < maxNum: newNumList[index] = -newNumList[index] index += 1 #5 return sum(newNumList)执行用时 :68 ms, 在所有 Python3 提交中击败了91.07%的用户，内存消耗 :13.9 MB, 在所有 Python3 提交中击败了5.25%的用户
C++实现
#include<map>#include<vector>class Solution {public: int romanToInt(string s) { map<char, int> charValue = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000},}; vector<int> valueList; reverse(s.begin(), s.end()); int listLength = s.size(); valueList.reserve(listLength); for(int i = 0; i < listLength; ++i) { valueList.push_back(charValue[s[i]]); } int maxNum = 0; for(int i = 0; i < listLength; ++i) { if(maxNum < valueList[i]) { maxNum = valueList[i]; } if(valueList[i] < maxNum) { valueList[i] = -valueList[i]; } } int sum = 0; for(int i = 0; i < listLength; ++i) { sum += valueList[i]; } return sum; }};执行用时 :44 ms, 在所有 C++ 提交中击败了28.45%的用户，内存消耗 :10.8 MB, 在所有 C++ 提交中击败了77.16%的用户