力扣解题-罗马数字转整数-平芜编程栈

力扣解题-罗马数字转整数

题目：
罗马数字包含以下七种字符: 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 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - 百度百科。

Related Topics
哈希表
数学
字符串

第一次解答

解题思路

核心方法：哈希表全量存储映射关系 + 优先匹配双字符特例，直接覆盖所有罗马数字（单字符/双字符）的数值映射，遍历字符串时优先判断是否为双字符特例，逻辑直观但哈希表查找存在一定开销。

具体步骤：

初始化HashMap，预存所有罗马数字的数值映射：包括7个单字符（如"I"→1、"V"→5）和6个双字符特例（如"IV"→4、"CM"→900），覆盖所有可能的罗马数字组合。
初始化累加和sum = 0，用于存储最终转换结果。
从左到右遍历罗马数字字符串s的每个下标i：
a. 优先判断是否能取到双字符（即i+1 < s.length()），且该双字符存在于哈希表中（说明是特殊组合）。
b. 若满足双字符匹配条件：将哈希表中该双字符对应的数值累加到sum，并将下标i自增1（跳过已匹配的第二个字符，避免重复处理）。
c. 若不满足双字符匹配条件：截取当前单字符，从哈希表中获取对应数值并累加到sum。
遍历完成后，返回累加和sum。

执行耗时:9 ms,击败了9.34% 的Java用户
内存消耗:46.4 MB,击败了7.89% 的Java用户

publicintromanToInt(Strings){Map<String,Integer>map=newHashMap<>();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);map.put("IV",4);map.put("IX",9);map.put("XL",40);map.put("XC",90);map.put("CD",400);map.put("CM",900);intsum=0;for(inti=0;i<s.length();i++){//判断是否为两个字符if(i+1<s.length()&&map.containsKey(s.substring(i,i+2))){sum+=map.get(s.substring(i,i+2));i++;}else{sum+=map.get(s.substring(i,i+1));}}returnsum;}

第二次解答

解题思路

核心方法：拆分字符串为单/双字符 + 自定义switch方法替代哈希表，移除哈希表的存储和查找开销，通过硬编码的switch语句直接返回数值，提升查找效率，优化性能。

具体步骤：

初始化累加和sum = 0，用于存储最终转换结果。
从左到右遍历罗马数字字符串s的每个下标i：
a. 先判断是否能取到双字符（i+1 < s.length()）：若能，则截取双字符并传入自定义方法getValueDouble()。
b.getValueDouble()通过switch语句匹配6个双字符特例，匹配成功则返回对应数值，否则返回0。
c. 若getValueDouble()返回值不为0（说明是双字符特例）：将该值累加到sum，并将下标i自增1（跳过第二个字符）。
d. 若getValueDouble()返回值为0（说明是单字符）：截取当前单字符传入自定义方法getValueBySingle()，该方法通过switch语句返回单字符对应的数值，并累加到sum。
e. 若已遍历到字符串最后一个字符（无法取双字符）：直接调用getValueBySingle()获取单字符数值并累加。
遍历完成后，返回累加和sum。

核心优化点说明：

用switch硬编码方法替代哈希表，避免了哈希表的初始化、存储和键值查找开销，是耗时从9ms降至5ms的核心原因。
拆分单/双字符的数值获取逻辑为两个独立方法，代码结构更清晰，职责更单一。

执行耗时:5 ms,击败了68.12% 的Java用户
内存消耗:45.8 MB,击败了38.18% 的Java用户

publicintromanToInt(Strings){intsum=0;for(inti=0;i<s.length();i++){if(i+1<s.length()){Stringparam=s.substring(i,i+2);intvalue=getValueDouble(param);if(value!=0){sum+=value;i++;}else{sum+=getValueBySingle(s.substring(i,i+1));}}else{sum+=getValueBySingle(s.substring(i,i+1));}}returnsum;}publicintgetValueDouble(Stringch){switch(ch){case"IV":return4;case"IX":return9;case"XL":return40;case"XC":return90;case"CD":return400;case"CM":return900;default:return0;}}publicintgetValueBySingle(Stringch){switch(ch){case"I":return1;case"V":return5;case"X":return10;case"L":return50;case"C":return100;case"D":return500;case"M":return1000;default:return0;}}

第三次解答

解题思路

核心方法：利用罗马数字数值规律 + 从右往左遍历，无需处理双字符特例，仅存储单字符映射，通过“大数加、小数减”的规则简化逻辑，进一步优化代码简洁性。

具体步骤：

初始化Map存储7个单字符罗马数字的数值映射（仅单字符，无需存储双字符特例），简化映射关系。
初始化累加和sum = 0，以及最大值标记max = 0（用于记录遍历过程中遇到的最大罗马数字值）。
从右往左遍历罗马数字字符串s的每个下标i（核心逻辑：罗马数字的本质是“大数在前则加，小数在前则减”，从右往左遍历可通过对比当前值与最大值实现该规则）：
a. 获取当前字符对应的数值value = map.get(s.charAt(i))。
b. 若value >= max：说明当前值是遍历至今的最大值，符合“大数在前”的规则，将value累加到sum，并更新max = value。
c. 若value < max：说明当前值是“小数在前”的特例（如IV中的I、CM中的C），从sum中减去该value。
遍历完成后，返回累加和sum。

核心优化点说明：

完全摒弃双字符处理逻辑，仅依赖罗马数字的数值规律，代码行数更少、逻辑更简洁。
仅存储单字符映射，减少内存占用；遍历过程中无字符截取操作，进一步降低开销。

publicintromanToInt(Strings){Map<Character,Integer>map=Map.of('I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000);intsum=0;intmax=0;for(inti=s.length()-1;i>=0;i--){intvalue=map.get(s.charAt(i));if(value>=max){sum+=value;max=value;}else{sum-=value;}}returnsum;}