Roman to Integer
罗马数字使用 7 个符号：I = 1，V = 5，X = 10，L = 50，C = 100，D = 500，M = 1000。除 6 种减法组合外，符号按从大到小的顺序书写并相加。在这 6 种组合中，较小的符号写在前面，并从较大的符号中减去：IV = 4，IX = 9，XL = 40，XC = 90，CD = 400，CM = 900。
给你一个有效的罗马数字 s。返回它所表示的整数。
函数
- sstring
- 一个有效的大写罗马数字
- 返回值integer
- 数字的值，范围为 1 到 3999
约束条件
1 ≤ s.length ≤ 15s只包含字符I、V、X、L、C、D和M。s是表示 1 到 3999 之间某个值的有效罗马数字。
示例
- 输入
- s = "XXVII"
- 输出
- 27
- 解释
XX是 10 + 10，V是 5，II是 1 + 1，所以总数是 27。没有符号后面跟着更大的符号，因此每个符号都会相加。
- 输入
- s = "CDXLIV"
- 输出
- 444
- 解释
- 这个数字是三个连续的减法组合：
CD是 400，XL是 40，IV是 4，因此结果是 444。
- 输入
- s = "MCDXCII"
- 输出
- 1492
- 解释
M表示 1000，CD表示 400，XC表示 90，II表示 2，所以这个数字是 1492。成对符号和单个符号可以自由组合。
进阶
你能写出相反的转换吗？把一个 1 到 3999 之间的整数转换成罗马数字。
提示
逐个打开提示，每个都会多透露一点。
把这个数字按符号逐个写成数值。
MCDXCII对应 1000、100、500、10、100、1、1。为了让总和等于 1492，其中哪些数值应算作负数？只有当一个符号后面的符号数值更大时，这个符号才需要减去：例如
CD中的 C、XC中的 X。其他所有符号都要相加，包括后面跟着相同符号的情况，例如II。用索引遍历字符串一次。比较当前符号的值和下一个符号的值，如果当前符号的值较小，就减去当前值；否则就加上当前值。最后一个符号没有相邻符号，所以总是将它加上。
题解
罗马数字的大部分都可以直接相加，因此关键是找出 6 个减法组合。你可以把它们当作两个字母的组合来查找，也可以用一条规则涵盖全部 6 个组合：如果一个符号的值小于右边相邻符号的值，就将它减去。无论用哪种方法，只需遍历一遍就能得出答案。
将减法配对视为标记
思路
把罗马数字看作一串记号：单个符号，以及 6 个双字符组合 IV、IX、XL、XC、CD 和 CM。把这些记号的值相加，就得到这个数字。MCDXCII 可拆分为 M、CD、XC、I、I：1000 + 400 + 90 + 1 + 1 = 1492。
先检查双字符组合，再检查单个符号，否则 XC 中的 X 会先加 10，然后再加 100。这种检查是安全的：在有效的罗马数字中，较小的符号只有在这几种组合中才会紧挨在较大的符号前面，因此找到的每个组合都确实有效。
每一步都会处理一个或两个字符，查找表的大小固定：时间复杂度为 O(n)，额外空间复杂度为 O(1)。
算法
- 为六个符号对创建一张表，为七个单独符号创建另一张表。
- 从索引 0 开始，总计值设为 0。
- 如果索引处的两个字符组成一个符号对，就加上该符号对的值，并将索引增加 2。
- 否则，加上单个符号的值，并将索引增加 1。
- 当索引超出末尾时，返回总计值。
def romanToInt(s):
pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
i = 0
while i < len(s):
two = s[i:i + 2]
if two in pairs:
total += pairs[two]
i += 2
else:
total += singles[s[i]]
i += 1
return total将每个符号与下一个符号进行比较
思路
在这六组符号中，每组的第一个符号都比第二个符号小，每组的值等于第二个符号减去第一个符号。因此，你可以去掉成对符号表，只使用一条规则：如果一个符号的值小于它右边相邻符号的值，就减去它；其他符号都加上。CM 的计算结果是 -100 + 1000 = 900，这与按令牌读取时得到的值相同。
在 MCDXCII 中，C 后面是更大的 D，X 后面是更大的 C，因此总值为 1000 - 100 + 500 - 10 + 100 + 1 + 1 = 1492。比较条件是严格小于：相邻符号相等时要相加，因此 II 的值是 2。这个规则之所以正确，原因与令牌相同：较小的符号只有在作为一对符号的前半部分时，才会紧挨在较大符号前面。
每个字符只查看一次，并维护一个总值：时间复杂度为 O(n)，额外空间复杂度为 O(1)。
算法
- 存储七个符号中每个符号的值。
- 遍历
s的索引，并用一个从 0 开始的累计总和。 - 如果下一个符号存在，并且它的值大于当前符号的值，就减去当前值。
- 否则，加上当前值。
- 循环结束后返回总和。
def romanToInt(s):
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
value = values[s[i]]
# A symbol worth less than the one after it is subtracted, like the I in IV.
if i + 1 < len(s) and value < values[s[i + 1]]:
total -= value
else:
total += value
return total
易错点和边界情况
- 使用小于等于，而不是严格小于。这样，
II和XX的结果都会是 0，因为每个字符串的第一个符号都会被减去。 - 在最后一个字符处读取不存在的
s[i+1]。先检查i+1是否小于字符串长度，并且始终加上最后一个符号。 - 在令牌版本中，先尝试单个符号，再尝试符号对。这样，
XC会被解析为 10 + 100 = 110。 - 忘记了 Lua 和 R 字符串的索引从 1 开始，所以最后一个符号位于
#s或nchar(s)。
常见问题3
罗马数字转整数的时间复杂度是多少？
这两种方法都会读取每个字符一次，因此对于包含 n 个字符的数字，时间复杂度为 O(n)。额外空间复杂度为 O(1)，因为查找表的大小固定。从 1 到 3999 的数字最多有 15 个字符。
你能从右向左转换一个罗马数字吗？
是的。从最后一个符号向前遍历到第一个符号，并记住右边那个符号的值。如果当前符号的值小于右边那个符号，就减去它；否则就加上它。这和从左到右的版本遵循同一条规则，只是从另一边来看。
这个答案会检查数字是否合法吗？
不。题目保证输入的是有效的数字，因此代码只进行加法和减法。像 IIII 或 VV 这样的无效字符串仍会返回一个数字，分别是 4 或 10。要进行验证，请将结果转换回数字，并与输入进行比较。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def romanToInt(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "XXVII"
预期输出
27