Leetcode 罗马数字转整数

代码的算法思想可以分为以下几步：

1. 建立映射表：

   • 首先，代码使用 HashMap 来存储罗马数字字符与其对应的整数值关系。例如，I 对应 1，V 对应 5，以此类推。这是为了方便后续快速查找每个罗马字符对应的整数值。

2. 从右向左遍历罗马数字字符串：

   • 代码从字符串的右边（最低位）开始，逐个字符地向左遍历。这是因为罗马数字中，如果一个较小的数出现在较大的数的左边，则需要从总数中减去该小数。通过从右向左遍历，可以更方便地处理这种减法规则。

3. 累加或减去对应值：

   • 遍历过程中，对于每个字符，首先查找它在映射表中的整数值。
   • 如果当前字符的值小于前一个字符的值（比如 IV 中的 I 小于 V），则说明需要执行减法，将当前值从结果中减去。
   • 如果当前字符的值大于或等于前一个字符的值，则说明需要执行加法，将当前值加到结果中。

4. 更新前一个字符的值：

   • 在每次循环中，将当前字符的值更新为 “前一个字符的值”，以便下一次循环使用。这是为了在下一个字符判断时，可以对比当前值与前一个字符的值，决定是加法还是减法。

5. 输出最终结果：

   • 遍历完成后，result 变量中存储的就是整个罗马数字字符串对应的整数值。

示例解释

以字符串 "MCMXCIV" 为例：

• 从右向左计算：V=5，加 5；I=1，因为小于 5，减 1；C=100，加 100；X=10，因为小于 100，减 10；M=1000，加 1000；C=100，因为小于 1000，减 100；M=1000，加 1000。
• 最终得到的结果是 1994。

算法复杂度

该算法的时间复杂度为 (O(n))，其中 (n) 为罗马数字字符串的长度。

java 代码实现

class Solution {public int romanToInt(String s) {Map<Character, Integer> map =  new HashMap<>();map.put('I', 1);map.put('V', 5);map.put('X', 10);map.put('L', 50);map.put('C', 100);map.put('D', 500);map.put('M', 1000);//设置一个变量来记录前一个位置的数值int prevValue = 0;//设置一个变量来存储最终结果int result = 0;for(int i = s.length() - 1; i >= 0; i--) {//获取当前位置的数值int currentValue = map.get(s.charAt(i));if(currentValue < prevValue) {result -= currentValue;}else {result += currentValue;}prevValue = currentValue;}return result;}
}