企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇是「算法通关手册（AlgoNote）」题解系列的第 0013 题精讲，围绕 LeetCode 经典简单题「罗马数字转整数」展开：先厘清罗马数字的加法/减法组合规则，再给出以哈希表建立「符号 → 数值」映射、单趟遍历完成转换的 Python 解法，并逐行拆解其正确性、复杂度与边界情况。读完本文，你将掌握「用哈希表做字符映射 + 相邻符号大小比较」这一处理符号转换类字符串题目的通用套路，并能在 题解索引 中继续追踪与之互为逆运算的 0012. 整数转罗马数字。

一、题目概述

题目：给定一个罗马数字字符串，将其转换为对应的整数。

• 标签：哈希表、数学、字符串
• 难度：简单
• 题解位置：docs/solutions/0001-0099/roman-to-integer.md

该题是 LeetCode 前 100 题中典型的「字符串 + 数学 + 数据结构」入门题，与 0012 题（整数转罗马数字）互为逆运算，常被作为哈希表章节的入门练习。在本书的 LeetCode 题解清单 中，这两题均标注为「哈希表、数学、字符串」标签，属于字符串类哈希表应用的基础题。

二、罗马数字规则（解题前提）

在动手写代码前，必须先明确罗马数字的数值组成规则。本题涉及的核心规则如下：

• 基础符号：I 代表数值 1，V 代表数值 5，X 代表数值 10，L 代表数值 50，C 代表数值 100，D 代表数值 500，M 代表数值 1000；
• 加法规则（一般情况）：罗马数字较大数字在左边、较小数字在右边，此时整个数值为两者之和。例如XI = X + I = 10 + 1 = 11；
• 减法规则（例外情况）：当较小数字出现在较大数字左边时，此时值为后者减前者之差。例如IX = X - I = 10 - 1 = 9。

注意减法规则的常见组合在本题范围内主要体现为：IV = 4、IX = 9、XL = 40、XC = 90、CD = 400、CM = 900。这些组合在 0012 题「整数转罗马数字」中作为整体单位出现（integer-to-roman.md），而本题采用「相邻比较」的方式在扫描过程中隐式处理它们。

三、解题思路：哈希表映射 + 相邻比较

整体思路分两步：

1. 用哈希表建立「罗马符号 → 整数值」的映射，将 7 个基础符号全部登记在表中；
2. 遍历字符串，比较相邻两个符号的大小：
   • 若前一个符号的值 >= 后一个符号的值，按加法规则，累加前一个符号的值；
   • 若前一个符号的值 < 后一个符号的值，按减法规则，说明前一个符号与后一个符号构成「小左大右」的组合（如 IV、IX、XC 等），应从结果中减去前一个符号的值；
3. 遍历结束后，把最后一个符号的值补加到结果中。

这一思路的核心洞察在于：判断某个符号应当「加」还是「减」，只需看它与右侧相邻符号的大小关系，因此一次从左到右的扫描即可完成，无需预处理特殊组合。

哈希表在这里发挥的作用是「以 O(1) 时间完成符号到数值的映射」，这正对应本书 哈希表章节 中对哈希表的定义——通过「键 key」与「哈希函数 Hash(key)」将关键码直接映射到存储位置，从而高效完成查找。本题的哈希表规模固定（仅 7 个键），属于直接定址/小型映射表的典型应用，避免了逐个 if-elif 判断的低效与冗长。

四、代码实现与逐行讲解

原题解给出的 Python 实现如下（保持原样，注释为讲解而加）：

class Solution: def romanToInt(self, s: str) -> int: # 1. 建立罗马符号 -> 数值 的哈希映射表 nunbers = { "I" : 1, "V" : 5, "X" : 10, "L" : 50, "C" : 100, "D" : 500, "M" : 1000 } sum = 0 pre_num = nunbers[s[0]] # 取出第一个符号的值作为“前一个值” for i in range(1, len(s)): # 从第 2 个符号开始遍历 cur_num = nunbers[s[i]] # 当前符号的值 if pre_num < cur_num: # 小值在前、大值在后 -> 减法组合 sum -= pre_num else: # 前值 >= 后值 -> 加法 sum += pre_num pre_num = cur_num # 更新“前一个值”为当前值 sum += pre_num # 最后补上最后一个符号的值 return sum

逐行要点：

• 映射表的建立：字典nunbers将 7 个罗马符号映射为其数值。本题符号集合固定且数量极少，直接使用字典字面量即可；在 LeetCode 刷题环境下（Python 3）无需额外导入包；
• 首元素初始化：pre_num = nunbers[s[0]]先把第一个符号的值取出，作为待判断的「前值」；
• 单趟遍历：循环从索引1开始，依次取出当前符号值cur_num，与pre_num比较：
  • pre_num < cur_num：说明出现了「左小右大」的减法组合，例如IV（1 < 5）、IX（1 < 10）、XC（10 < 100），此时应把前值减去；
  • 否则（pre_num >= cur_num）：普通加法情形，把前值累加；
• 状态滚动：pre_num = cur_num使「前值」随遍历推进滚动更新，保证每次只比较相邻两个符号；
• 收尾累加：循环结束后，pre_num保存的是最后一个符号的值（它没有右邻符号可比，必然按加法计入），因此sum += pre_num补齐结果。

验证示例

以MCMXCIV（即 1994）为例模拟：

五、复杂度分析

• 时间复杂度：O(n)，其中 n 为罗马数字字符串的长度。只需一次从左到右的扫描，每次比较与字典查找均为 O(1)；
• 空间复杂度：O(1)。哈希表大小固定为 7 个键，不随输入规模增长。

由于罗马数字的表示在题目约束下长度有限，实际运行时间开销极小，属于最优级别的线性解法。

六、边界情况与正确性论证

• 长度为 1 的输入：如s = "V"，循环体不执行，直接sum += pre_num返回 5，正确；
• 全部为同值连续符号：如"III"，相邻比较均为pre >= cur，逐项累加得 1 + 1 + 1 = 3，正确；
• 混合加减组合：如"IV"，第一次比较1 < 5执行sum -= 1，收尾补加 5，得 4；"IX"同理得 9；
• 假设前提：本题输入保证是合法罗马数字（题目约束内），因此无需额外的合法性校验；若输入非法（如"IIII"、"VX"），该算法在题目约束外不保证结果语义，实际刷题时无需处理。

七、延伸：与 0012 题的互逆关系

与本题互为逆运算的 0012. 整数转罗马数字 采用贪心算法：把[1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I]按从大到小排列，每次用尽可能大的符号去整除并拼接。两道题共享同一套罗马数字规则，区别仅在于：

• 0013 题（本题）：字符串 → 整数，用哈希表 + 相邻比较；
• 0012 题：整数 → 字符串，用贪心 + 有序映射表。

建议两题对照练习：0012 题的映射表把IV/IX/XL/XC/CD/CM显式列为独立单位，而本题通过「左小右大则减」的规则在扫描中隐式覆盖了同一批组合——理解二者的等价关系，有助于吃透罗马数字的完整规则体系。

八、刷题路径建议

在「算法通关手册」中，本题的定位是哈希表标签下的入门实战。建议学习顺序：

1. 先阅读 哈希表基础章节，掌握哈希函数、哈希冲突（开放地址法与链地址法）的基本概念，理解「键值映射 + O(1) 查找」为何适合本题；
2. 独立完成本题实现，并尝试用「逐个 if-elif 判断」的笨办法对比，体会哈希表在代码简洁度上的优势；
3. 紧接着练习 0012. 整数转罗马数字，完成规则的正反向闭环；
4. 依据 LeetCode 题解清单 中的「哈希表」标签，继续刷 0001. 两数之和、0049. 字母异位词分组 等同类题目，巩固映射思维。

• 教程
• 文档
• 知识库