每日算法练习：LeetCode 13. 罗马数字转整数 ✅
大家好，我是你们的算法小伙伴。今天我们来练习一道字符串处理的经典题目 ——LeetCode 13. 罗马数字转整数。这道题考察对特殊规则的处理，是面试中常见的基础题。
题目描述
罗马数字包含以下七种字符：I，V，X，L，C，D，M，分别对应数值：
表格
| 字符 | 数值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
通常情况下，罗马数字中小的数字在大的数字的右边。但存在特例，例如：
IV= 4，IX= 9XL= 40，XC= 90CD= 400，CM= 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) { // 建立罗马字符到数值的映射 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 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 模拟）
示例 5：s = "MCMXCIV"→ 对应字符：M C M X C I V
表格
| i | 当前字符 | 当前值 | 下一个字符 | 下一个值 | 操作 | res |
|---|---|---|---|---|---|---|
| 0 | M | 1000 | C | 100 | 1000 ≥ 100 → +1000 | 1000 |
| 1 | C | 100 | M | 1000 | 100 < 1000 → -100 | 900 |
| 2 | M | 1000 | X | 10 | 1000 ≥ 10 → +1000 | 1900 |
| 3 | X | 10 | C | 100 | 10 < 100 → -10 | 1890 |
| 4 | C | 100 | I | 1 | 100 ≥ 1 → +100 | 1990 |
| 5 | I | 1 | V | 5 | 1 < 5 → -1 | 1989 |
| - | V | 5 | - | - | +5 | 1994 |
最终结果1994，与示例一致。
复杂度分析
- 时间复杂度：O (n)，遍历字符串一次。
- 空间复杂度：O (1)，映射表大小固定为 7，仅使用常数级额外空间。
总结
- 核心技巧：利用 “小数在大数左边则减法” 的规则，一次遍历完成转换。
- 代码简洁：通过哈希表快速查找字符对应数值，逻辑清晰易读。
- 边界处理：最后一个字符单独处理，避免数组越界。
这道题是字符串处理和规则判断的经典入门题，非常适合练习基础算法思维。
今天的每日算法练习就到这里，我们明天再见！👋