LeetCode 13. 罗马数字转整数

约 4 分钟
文章信息 12 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 面试经典 150 题 字节 微软 亚马逊 网易 旷视 猿辅导
标签
字符串 哈希表 数学

题目描述

✅ 13. 罗马数字转整数

image-20260928214555165

image-20260928214555166

题意分析

将一个合法的罗马数字字符串转换为整数。I、V、X、L、C、D、M 的数值依次是 $1、5、10、50、100、500、1000$，通常直接相加。

减法只出现在六种合法组合中：IV、IX、XL、XC、CD、CM，它们都是小值在前、大值在后。题目已经保证输入合法，因此只需计算数值，不需要再判断字符串是否符合罗马数字的书写规则。

解法：相邻值比较累加

核心思路

[!blue]

一个减法组合的数值是「后一个大值减去前一个小值」，可以把它拆成两个字符各自的贡献：前一个取负，后一个取正。这样就不必单独截取组合，仍可从左到右每次处理一个字符。

设当前字符映射后的数值为 cur，右侧相邻字符的数值为 next：

  • 若 cur < next，在合法输入中，当前字符一定是减法组合的左半部分，本轮将 cur 从答案中减去。
  • 否则，当前字符按加法计入答案。相同字符也属于这一分支，不能把判断写成小于等于。

合法的减法组合不会连续向右升高，因此组合的大值字符在下一轮会正常相加。其余字符也各自相加，累加完每个字符的贡献，就得到了整个罗马数字的数值。减去小值后无需跳过下一字符，否则会漏掉组合中的大值。

最后一个字符没有右邻，一定按加法处理。代码把此时的 next 设为 $0$；七种字符的值都大于 $0$，因此可以继续使用同一个比较规则，并避免访问越界。

解题步骤

  1. 建立七个罗马字符到整数的映射，将累计结果 ans 初始化为 $0$。
  2. 从左到右遍历字符串，读取当前值 cur；有右邻时读取 next，否则令 next = 0。
  3. 若 cur < next，执行 ans -= cur；否则执行 ans += cur。
  4. 每轮只前进一个字符，遍历结束后返回 ans。

代码实现

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> value = new HashMap<>();

        value.put('I', 1);
        value.put('V', 5);
        value.put('X', 10);
        value.put('L', 50);
        value.put('C', 100);
        value.put('D', 500);
        value.put('M', 1000);

        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            int cur = value.get(s.charAt(i));
            int next = i + 1 < s.length() ? value.get(s.charAt(i + 1)) : 0;

            // 当前值小于右邻值时作减法，末位的右邻零使其自然累加。
            ans += cur < next ? -cur : cur;
        }

        return ans;
    }
}

func romanToInt(s string) int {
    value := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    ans := 0
    for i := 0; i < len(s); i++ {
        cur := value[s[i]]
        next := 0
        if i+1 < len(s) {
            next = value[s[i+1]]
        }
        // 当前值小于右邻值时作减法，末位的右邻零使其自然累加。
        if cur < next {
            ans -= cur
        } else {
            ans += cur
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，每个字符只处理一次。
  • 空间复杂度：$O(1)$，映射表固定只有七项。

关键点总结

[!green]

  • 把减法组合拆为一个负贡献和一个正贡献，就能统一为逐字符累加。
  • 输入合法是相邻比较足够的前提；算法负责转换数值，不负责校验任意字符串。
  • 末位的右邻值设为 $0$，既统一了累加规则，也处理了边界。

易错点总结

[!yellow]

  • 无条件累加会把减法组合中的小值也加上，必须根据右邻数值决定符号。
  • 写成 cur <= next 会把重复字符错误当作减法组合。
  • 直接读取 s[i + 1] 会在最后一轮越界，必须判断边界或使用哨兵。
  • 字符编码顺序不代表罗马数字的大小，比较前必须先转换为数值。
  • 减去当前值后仍要处理下一字符，不能跳过减法组合中的大值。

相似题目

题目 难度 关联与区别
12. 整数转罗马数字 中等 反向过程是按数值构造罗马表示，可用同一组特殊减法组合理解解析规则。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/68898668
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！