13：罗马数值转换为整数
题目描述
题目：
罗马数字包含以下七种字符: I、V、X、L、C、D 和 M。给定一个罗马数字，将其转换成整数。
字符对应关系
| 字符 | 数值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
特殊规则
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如：
IV表示 4（5 - 1）IX表示 9（10 - 1）XL表示 40（50 - 10）XC表示 90（100 - 10）CD表示 400（500 - 100）CM表示 900（1000 - 100）
示例
示例 1：
输入: s = "III"
输出: 3
解释: III = 3
示例 2：
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3
提示
- 1 <= s.length <= 15
- s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
- 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
解题思路
- 建立罗马数字到整数的映射关系
- 从左到右遍历字符串
- 根据规则判断是加还是减：
- 如果当前字符代表的值小于其右边字符代表的值，则减去当前值
- 否则加上当前值
代码
方法 1
从左向右遍历，通过比较相邻字符来决定加减：
class Solution:
def romanToInt(self, s: str) -> int:
# 建立罗马数字到整数的映射
roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000}
result = 0 # 存储最终结果
# 遍历到倒数第二个字符
for index in range(len(s)-1):
if roman[s[index]] < roman[s[index+1]]:
result -= roman[s[index]] # 当前字符小于右边字符，减去当前值
else:
result += roman[s[index]] # 当前字符大于等于右边字符，加上当前值
return result + roman[s[-1]] # 加上最后一个字符的值
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度
- 空间复杂度：O(1)，只需要常数空间存储映射关系
方法 2
从右向左遍历，通过与前一个值比较来决定加减：
class Solution:
def romanToInt(self, s: str) -> int:
# 定义罗马数字的映射
roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
total = 0
prev_value = 0
for ch in reversed(s):
value = roman[ch]
if value < prev_value:
total -= value # 如果当前值小于前一个值，则减去当前值
else:
total += value # 否则，加上当前值
prev_value = value
return total
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法 3
直接遍历，通过检查下一个字符来决定加减：
class Solution:
def romanToInt(self, s: str) -> int:
roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000}
total = 0
i = 0
while i < len(s):
# 获取当前字符代表的值
value = roman[s[i]]
# 如果不是最后一个字符，并且当前字符代表的值小于下一个字符代表的值
if i + 1 < len(s) and value < roman[s[i + 1]]:
total -= value
else:
total += value
i += 1
return total
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法比较
- 方法一：适合从左到右的线性处理
- 方法二：通过反向遍历简化了判断逻辑
- 方法三：直观但需要额外的边界检查
注意：
- 确保输入是有效的罗马数字
- 注意特殊组合的处理
- 考虑边界情况
函数 reversed：reversed()指南