每日算法练习：LeetCode 13. 罗马数字转整数 ✅

大家好我是你们的算法小伙伴。今天我们来练习一道字符串处理的经典题目 ——LeetCode 13. 罗马数字转整数。这道题考察对特殊规则的处理是面试中常见的基础题。题目描述罗马数字包含以下七种字符IVXLCDM分别对应数值表格字符数值I1V5X10L50C100D500M1000通常情况下罗马数字中小的数字在大的数字的右边。但存在特例例如IV 4IX 9XL 40XC 90CD 400CM 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.解题思路核心规则正常情况左边数字 ≥ 右边数字→ 直接相加。特殊情况左边数字 右边数字→ 用右边数字减去左边数字相当于加上 “右边 - 左边”。算法步骤建立一个字符→数值的映射表HashMap或switch。遍历字符串如果当前字符数值 下一个字符数值 → 减去当前数值处理特例。否则 → 加上当前数值。最后一个字符没有下一个字符直接加上它的数值。代码实现import java.util.HashMap; import java.util.Map; class Solution { public int romanToInt(String s) { // 建立罗马字符到数值的映射 MapCharacter, 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 res 0; int n s.length(); for (int i 0; i n - 1; i) { int current map.get(s.charAt(i)); int next map.get(s.charAt(i 1)); // 处理特例当前值 下一个值减去当前值 if (current next) { res - current; } else { res current; } } // 加上最后一个字符的数值 res map.get(s.charAt(n - 1)); return res; } }代码详解示例 5 模拟示例 5s MCMXCIV→ 对应字符M C M X C I V表格i当前字符当前值下一个字符下一个值操作res0M1000C1001000 ≥ 100 → 100010001C100M1000100 1000 → -1009002M1000X101000 ≥ 10 → 100019003X10C10010 100 → -1018904C100I1100 ≥ 1 → 10019905I1V51 5 → -11989-V5--51994最终结果1994与示例一致。复杂度分析时间复杂度O (n)遍历字符串一次。空间复杂度O (1)映射表大小固定为 7仅使用常数级额外空间。总结核心技巧利用 “小数在大数左边则减法” 的规则一次遍历完成转换。代码简洁通过哈希表快速查找字符对应数值逻辑清晰易读。边界处理最后一个字符单独处理避免数组越界。这道题是字符串处理和规则判断的经典入门题非常适合练习基础算法思维。今天的每日算法练习就到这里我们明天再见