教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册AlgoNote」题解系列的第 0013 题精讲围绕 LeetCode 经典简单题「罗马数字转整数」展开先厘清罗马数字的加法/减法组合规则再给出以哈希表建立「符号 → 数值」映射、单趟遍历完成转换的 Python 解法并逐行拆解其正确性、复杂度与边界情况。读完本文你将掌握「用哈希表做字符映射 相邻符号大小比较」这一处理符号转换类字符串题目的通用套路并能在 题解索引 中继续追踪与之互为逆运算的 0012. 整数转罗马数字。一、题目概述题目给定一个罗马数字字符串将其转换为对应的整数。标签哈希表、数学、字符串难度简单题解位置docs/solutions/0001-0099/roman-to-integer.md该题是 LeetCode 前 100 题中典型的「字符串 数学 数据结构」入门题与 0012 题整数转罗马数字互为逆运算常被作为哈希表章节的入门练习。在本书的 LeetCode 题解清单 中这两题均标注为「哈希表、数学、字符串」标签属于字符串类哈希表应用的基础题。二、罗马数字规则解题前提在动手写代码前必须先明确罗马数字的数值组成规则。本题涉及的核心规则如下基础符号I 代表数值 1V 代表数值 5X 代表数值 10L 代表数值 50C 代表数值 100D 代表数值 500M 代表数值 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而本题采用「相邻比较」的方式在扫描过程中隐式处理它们。三、解题思路哈希表映射 相邻比较整体思路分两步用哈希表建立「罗马符号 → 整数值」的映射将 7 个基础符号全部登记在表中遍历字符串比较相邻两个符号的大小若前一个符号的值 后一个符号的值按加法规则累加前一个符号的值若前一个符号的值 后一个符号的值按减法规则说明前一个符号与后一个符号构成「小左大右」的组合如 IV、IX、XC 等应从结果中减去前一个符号的值遍历结束后把最后一个符号的值补加到结果中。这一思路的核心洞察在于判断某个符号应当「加」还是「减」只需看它与右侧相邻符号的大小关系因此一次从左到右的扫描即可完成无需预处理特殊组合。哈希表在这里发挥的作用是「以 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说明出现了「左小右大」的减法组合例如IV1 5、IX1 10、XC10 100此时应把前值减去否则pre_num cur_num普通加法情形把前值累加状态滚动pre_num cur_num使「前值」随遍历推进滚动更新保证每次只比较相邻两个符号收尾累加循环结束后pre_num保存的是最后一个符号的值它没有右邻符号可比必然按加法计入因此sum pre_num补齐结果。验证示例以MCMXCIV即 1994为例模拟步骤当前比较判定累计结果1M(1000) vs C(100)前 后加 100010002C(100) vs M(1000)前 后减 1009003M(1000) vs X(10)前 后加 100019004X(10) vs C(100)前 后减 1018905C(100) vs I(1)前 后加 10019906I(1) vs V(5)前 后减 11989收尾补加 V(5)—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得 4IX同理得 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显式列为独立单位而本题通过「左小右大则减」的规则在扫描中隐式覆盖了同一批组合——理解二者的等价关系有助于吃透罗马数字的完整规则体系。八、刷题路径建议在「算法通关手册」中本题的定位是哈希表标签下的入门实战。建议学习顺序先阅读 哈希表基础章节掌握哈希函数、哈希冲突开放地址法与链地址法的基本概念理解「键值映射 O(1) 查找」为何适合本题独立完成本题实现并尝试用「逐个 if-elif 判断」的笨办法对比体会哈希表在代码简洁度上的优势紧接着练习 0012. 整数转罗马数字完成规则的正反向闭环依据 LeetCode 题解清单 中的「哈希表」标签继续刷 0001. 两数之和、0049. 字母异位词分组 等同类题目巩固映射思维。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GLFW 入门10 分钟搭好一个能跑的跨平台 OpenGL 窗口GLFW 入门10 分钟搭好一个能跑的跨平台 OpenGL 窗口 GLFW 是一个跨平台的 C 语言库负责帮你建窗口、收输入、管理 OpenGL / Ope教程文档知识库LeetCode 0013 罗马数字转整数Roman to Integer哈希表与相邻字符比较的单遍扫描解法LeetCode 0013 罗马数字转整数Roman to Integer哈希表与相邻字符比较的单遍扫描解法 导读 本文基于仓库 articles/rom示例工程教程AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析 本篇技术指南围绕 LeetCode 第 00教程文档知识库上一篇Jekyll 3.8.6 补丁版详解主题 Gem 符号链接安全加固、Liquid 摘要修复与内存优化下一篇League Akari 上手本地化的英雄联盟效率工具如何把自动选人压缩进 10 秒创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
