罗马数字转整数

难度:

标签:

题目描述

罗马数字包含以下七种字符: 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:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

代码结果

运行时间: 56 ms, 内存: 14.8 MB

/*
 * 思路: 使用Java Streams实现同样的逻辑, 通过反转字符串流, 然后根据罗马数字的值累加或减去.
 */
import java.util.*;
 
public class RomanToIntStream {
    public int romanToInt(String s) {
        Map<Character, Integer> romanMap = Map.of(
            'I', 1, 'V', 5, 'X', 10, 'L', 50,
            'C', 100, 'D', 500, 'M', 1000
        );
 
        int[] prevValue = {0};
        return new StringBuilder(s).reverse().chars()
            .map(c -> romanMap.get((char) c))
            .map(currentValue -> {
                if (currentValue < prevValue[0]) {
                    prevValue[0] = currentValue;
                    return -currentValue;
                } else {
                    prevValue[0] = currentValue;
                    return currentValue;
                }
            })
            .sum();
    }
}

解释

方法:

这个题解的思路是从左到右遍历罗马数字字符串，用一个哈希表 m 存储每个罗马数字字符对应的整数值。遍历时，用 pre_num 记录上一个字符对应的整数值，cur_num 记录当前字符对应的整数值。如果 pre_num < cur_num，说明这是一个特殊情况，需要减去 pre_num；否则，将 pre_num 加到结果 ans 中。最后，将最后一个字符对应的整数值加到 ans 中，即为最终结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

你是如何确定哈希表中包含的罗马数字和整数映射是正确和完整的？

▷

哈希表中包含的罗马数字到整数的映射是根据罗马数字的标准定义建立的。罗马数字系统中的每个基本字符（I, V, X, L, C, D, M）都有一个固定的整数值。此映射是历史和数学上公认的，因此可以确保其正确性和完整性。

🦆

在处理特殊规则时，`pre_num < cur_num`这个条件如何确保不会出现误判，比如在处理字符串`III`时？

▷

在处理字符串时，`pre_num < cur_num`这个条件用于检测特殊的罗马数字减法规则，例如IV、IX。在`III`这样的字符串中，由于每个字符代表的值相等，`pre_num`不会小于`cur_num`，因此每次循环都会执行加法操作。这个条件确保只有在真正需要进行减法操作时（即遇到特定的字符组合），才会执行减法。

🦆

为什么在循环结束后还需要加上`pre_num`到`ans`中，这是否意味着每次循环并未完全处理每个字符的值？

▷

在循环中，我们处理的是当前字符和前一个字符之间的关系。由于循环从第二个字符开始，第一个字符的值在开始时被赋予`pre_num`但未立即加入到`ans`中。循环确保每次处理完当前字符后，将`pre_num`（即前一个字符的值）正确加入到`ans`。循环结束后，最后一个字符的值（存储在`pre_num`中）还未被加入，因此需要在循环后将其加入`ans`中。

🦆

在设计这个算法时，如何考虑到字符串长度和特殊规则处理对时间复杂度的影响？

▷

算法的时间复杂度主要受字符串长度的影响，为O(n)，其中n是字符串的长度。由于每个字符最多只需要比较一次（与前一个字符比较），所以时间复杂度是线性的。特殊规则的处理（使用`pre_num < cur_num`条件）不增加额外的循环或复杂的操作，因此不会显著影响算法的时间复杂度。

🦆

为什么选择从左到右而不是从右到左遍历字符串进行数值计算？从右到左是否会更符合罗马数字的读取习惯？

▷

虽然从右到左计算可以直接处理数值累加，但从左到右遍历可以更直观地识别并处理罗马数字中的特殊减法规则（如IV、IX等）。此外，从左到右遍历是大多数语言和算法中的常见模式，这可以减少错误并增加代码的可读性。实际上，两种遍历方法都可以正确计算罗马数字，选择哪一种主要取决于实现的简便性和个人偏好。

🦆

如果输入的罗马数字字符串包含非法字符，如何修改算法以便能够检测并处理这种错误？

▷

为了处理包含非法字符的情况，可以在遍历字符串之前添加一个验证步骤，检查字符串中的每个字符是否都存在于罗马数字的哈希表中。如果发现任何字符不在哈希表中，可以抛出一个异常或返回一个特定的错误代码。这样可以在计算开始之前识别非法输入，防止进一步的错误计算。

罗马数字转整数

题目描述

代码结果

解释

代码细节讲解

相关问题

整数转罗马数字