013.罗马数字转整数
作者：沉默王二 发布时间：2024-01-22T11:17:31.029+0800
技术派阅读地址：https://paicoding.com/column/7/1 3
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出2道大家完全都能掌握的题解（hashmap 和 数组）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，三天不刷 LeetCode，手里发痒，今天继续来刷《二哥的 LeetCode 刷题笔记》吧。
题意
给你一个罗马数字，要求你给出它相应的整数。
至于罗马数字是什么，**第 12 题 **已经解释过了，这里就不再赘述。
难度
简单
示例
示例 1:
输入:s="III"
示例 2:
输入:s="IV"
示例 3:
输入:s="IX"
示例 4:
输入:s="LVIII"
解释:L=50,V=5,III=3.
示例 5:
输入:s="MCMXCIV"
解释:M=1000,CM=900,XC=90,IV=4.
分析 1
这道题目和**第 12 题 是相反的，第 12 题 **是整数转罗马数字，这道题目是罗马数字转整数。
我们可以先把罗马数字和整数的对应关系列出来：
我们可以发现，罗马数字和整数的对应关系是一一对应的，所以我们可以把这些对应关系放到一个 Map 中，然后遍历罗马数字，依次取出对应的整数，然后相加即可。
需要注意的是，如果一个较小的数字在较大的数字前面，比如 IV、IX、XL、XC、CD、CM，需要减去这个较小的数字（因为它表示的是一个减法操作，如 IV 表示 4）。
来看题解：
class Solution {
// 创建一个哈希表存储罗马数字和对应的整数值 Map<Character, Integer> romanMap = new HashMap<>(); romanMap.put('I', 1); romanMap.put('V', 5); romanMap.put('X', 10); romanMap.put('L', 50); romanMap.put('C', 100); romanMap.put('D', 500); romanMap.put('M', 1000);
int sum = 0; int prevValue = 0;
// 从后向前遍历罗马数字字符串 for (int i = s.length() - 1; i >= 0; i--) { int currValue = romanMap.get(s.charAt(i));
// 如果当前值小于之前的值，则减去当前值；否则，加上当前值 if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
我们首先创建一个**哈希表 **来存储罗马数字字符及其对应的整数值。
然后，从字符串的最后一个字符开始向前遍历（这样可以更方便地处理减法情况）。
对于每个字符，我们查找其对应的整数值。
如果当前字符代表的数值小于其右侧的数值，这意味着我们遇到了一个减法情况（如 IV 或 IX），因此我们从总和中减去这个数值。
如果当前字符代表的数值大于等于其右侧的数值，我们就简单地加上这个数值。
最终累加的结果就是罗马数字字符串所表示的整数值。
来看一下题解效率，还不错：
分析 2
我们可以把上面的代码再优化一下，把 Map 换成数组，这样效率会更高一点。
class Solution {
int[] values = new int[128]; // ASCII 码的范围足够覆盖所有字符 values['I'] = 1; values['V'] = 5; values['X'] = 10; values['L'] = 50; values['C'] = 100; values['D'] = 500; values['M'] = 1000;
int sum = 0; int prevValue = 0;
for (int i = s.length() - 1; i >= 0; i--) { int currValue = values[s.charAt(i)];
if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
除了把 Map 换成数组，其他的代码都是一样的。所以我就没再加注释，来看一下效率提升：
OK，这次 beat 100% 了，效率提升了一大截。
这里需要注意的是，数组的长度为 128，这是基于 ASCII 码的范围设计的。ASCII 码是一种字符编码标准，它将英文字符、数字、标点符号等映射到 0-127 的整数上。
当使用字符 int currValue = values[s.charAt(i)] 作为数组索引时，字符实际上被转换为其对应的 ASCII 值。例如，字符 'A' 对应 ASCII 值 65。
使用 128 大小的数组可以确保直接通过字符的 ASCII 值作为索引来访问数组元素，这样的访问速度更快。
虽然题目中只用到了 7 个罗马字符，但这样可以确保代码的通用性。这是另外一个非常巧妙的地方。
总结
这道题的巧妙之处就在于：对于罗马数字来说，把一个小值放在大值的左边，就是做减法，否则为加法。
剩下的处理就非常简单了。由于罗马数字的数量非常有限，总共就 7 个，仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')，我们也可以通过数组来替代 HashMap，这样的效率会更快一点，虽然 HashMap 的底层也是数组。但毕竟 HashMap 是对数组的一种封装，加上了链表和红黑树，包括扩容等操作，所以效率肯定没有直接使用数组来得高。
这道题目所涉及到的 Java 基础知识有：
力扣链接：https://leetcode.cn/problems/roman-to-integer/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/1 3
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出2道大家完全都能掌握的题解（hashmap 和 数组）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，三天不刷 LeetCode，手里发痒，今天继续来刷《二哥的 LeetCode 刷题笔记》吧。
题意
给你一个罗马数字，要求你给出它相应的整数。
至于罗马数字是什么，**第 12 题 **已经解释过了，这里就不再赘述。
难度
简单
示例
示例 1:
输入:s="III"
示例 2:
输入:s="IV"
示例 3:
输入:s="IX"
示例 4:
输入:s="LVIII"
解释:L=50,V=5,III=3.
示例 5:
输入:s="MCMXCIV"
解释:M=1000,CM=900,XC=90,IV=4.
分析 1
这道题目和**第 12 题 是相反的，第 12 题 **是整数转罗马数字，这道题目是罗马数字转整数。
我们可以先把罗马数字和整数的对应关系列出来：
我们可以发现，罗马数字和整数的对应关系是一一对应的，所以我们可以把这些对应关系放到一个 Map 中，然后遍历罗马数字，依次取出对应的整数，然后相加即可。
需要注意的是，如果一个较小的数字在较大的数字前面，比如 IV、IX、XL、XC、CD、CM，需要减去这个较小的数字（因为它表示的是一个减法操作，如 IV 表示 4）。
来看题解：
class Solution {
// 创建一个哈希表存储罗马数字和对应的整数值 Map<Character, Integer> romanMap = new HashMap<>(); romanMap.put('I', 1); romanMap.put('V', 5); romanMap.put('X', 10); romanMap.put('L', 50); romanMap.put('C', 100); romanMap.put('D', 500); romanMap.put('M', 1000);
int sum = 0; int prevValue = 0;
// 从后向前遍历罗马数字字符串 for (int i = s.length() - 1; i >= 0; i--) { int currValue = romanMap.get(s.charAt(i));
// 如果当前值小于之前的值，则减去当前值；否则，加上当前值 if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
我们首先创建一个**哈希表 **来存储罗马数字字符及其对应的整数值。
然后，从字符串的最后一个字符开始向前遍历（这样可以更方便地处理减法情况）。
对于每个字符，我们查找其对应的整数值。
如果当前字符代表的数值小于其右侧的数值，这意味着我们遇到了一个减法情况（如 IV 或 IX），因此我们从总和中减去这个数值。
如果当前字符代表的数值大于等于其右侧的数值，我们就简单地加上这个数值。
最终累加的结果就是罗马数字字符串所表示的整数值。
来看一下题解效率，还不错：
分析 2
我们可以把上面的代码再优化一下，把 Map 换成数组，这样效率会更高一点。
class Solution {
int[] values = new int[128]; // ASCII 码的范围足够覆盖所有字符 values['I'] = 1; values['V'] = 5; values['X'] = 10; values['L'] = 50; values['C'] = 100; values['D'] = 500; values['M'] = 1000;
int sum = 0; int prevValue = 0;
for (int i = s.length() - 1; i >= 0; i--) { int currValue = values[s.charAt(i)];
if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
除了把 Map 换成数组，其他的代码都是一样的。所以我就没再加注释，来看一下效率提升：
OK，这次 beat 100% 了，效率提升了一大截。
这里需要注意的是，数组的长度为 128，这是基于 ASCII 码的范围设计的。ASCII 码是一种字符编码标准，它将英文字符、数字、标点符号等映射到 0-127 的整数上。
当使用字符 int currValue = values[s.charAt(i)] 作为数组索引时，字符实际上被转换为其对应的 ASCII 值。例如，字符 'A' 对应 ASCII 值 65。
使用 128 大小的数组可以确保直接通过字符的 ASCII 值作为索引来访问数组元素，这样的访问速度更快。
虽然题目中只用到了 7 个罗马字符，但这样可以确保代码的通用性。这是另外一个非常巧妙的地方。
总结
这道题的巧妙之处就在于：对于罗马数字来说，把一个小值放在大值的左边，就是做减法，否则为加法。
剩下的处理就非常简单了。由于罗马数字的数量非常有限，总共就 7 个，仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')，我们也可以通过数组来替代 HashMap，这样的效率会更快一点，虽然 HashMap 的底层也是数组。但毕竟 HashMap 是对数组的一种封装，加上了链表和红黑树，包括扩容等操作，所以效率肯定没有直接使用数组来得高。
这道题目所涉及到的 Java 基础知识有：
力扣链接：https://leetcode.cn/problems/roman-to-integer/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/1 3
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出2道大家完全都能掌握的题解（hashmap 和 数组）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，三天不刷 LeetCode，手里发痒，今天继续来刷《二哥的 LeetCode 刷题笔记》吧。
题意
给你一个罗马数字，要求你给出它相应的整数。
至于罗马数字是什么，**第 12 题 **已经解释过了，这里就不再赘述。
难度
简单
示例
示例 1:
输入:s="III"
示例 2:
输入:s="IV"
示例 3:
输入:s="IX"
示例 4:
输入:s="LVIII"
解释:L=50,V=5,III=3.
示例 5:
输入:s="MCMXCIV"
解释:M=1000,CM=900,XC=90,IV=4.
分析 1
这道题目和**第 12 题 是相反的，第 12 题 **是整数转罗马数字，这道题目是罗马数字转整数。
我们可以先把罗马数字和整数的对应关系列出来：
我们可以发现，罗马数字和整数的对应关系是一一对应的，所以我们可以把这些对应关系放到一个 Map 中，然后遍历罗马数字，依次取出对应的整数，然后相加即可。
需要注意的是，如果一个较小的数字在较大的数字前面，比如 IV、IX、XL、XC、CD、CM，需要减去这个较小的数字（因为它表示的是一个减法操作，如 IV 表示 4）。
来看题解：
class Solution {
// 创建一个哈希表存储罗马数字和对应的整数值 Map<Character, Integer> romanMap = new HashMap<>(); romanMap.put('I', 1); romanMap.put('V', 5); romanMap.put('X', 10); romanMap.put('L', 50); romanMap.put('C', 100); romanMap.put('D', 500); romanMap.put('M', 1000);
int sum = 0; int prevValue = 0;
// 从后向前遍历罗马数字字符串 for (int i = s.length() - 1; i >= 0; i--) { int currValue = romanMap.get(s.charAt(i));
// 如果当前值小于之前的值，则减去当前值；否则，加上当前值 if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
我们首先创建一个**哈希表 **来存储罗马数字字符及其对应的整数值。
然后，从字符串的最后一个字符开始向前遍历（这样可以更方便地处理减法情况）。
对于每个字符，我们查找其对应的整数值。
如果当前字符代表的数值小于其右侧的数值，这意味着我们遇到了一个减法情况（如 IV 或 IX），因此我们从总和中减去这个数值。
如果当前字符代表的数值大于等于其右侧的数值，我们就简单地加上这个数值。
最终累加的结果就是罗马数字字符串所表示的整数值。
来看一下题解效率，还不错：
分析 2
我们可以把上面的代码再优化一下，把 Map 换成数组，这样效率会更高一点。
class Solution {
int[] values = new int[128]; // ASCII 码的范围足够覆盖所有字符 values['I'] = 1; values['V'] = 5; values['X'] = 10; values['L'] = 50; values['C'] = 100; values['D'] = 500; values['M'] = 1000;
int sum = 0; int prevValue = 0;
for (int i = s.length() - 1; i >= 0; i--) { int currValue = values[s.charAt(i)];
if (currValue < prevValue) { sum -= currValue; } else { sum += currValue; } prevValue = currValue; }
return sum; }}
除了把 Map 换成数组，其他的代码都是一样的。所以我就没再加注释，来看一下效率提升：
OK，这次 beat 100% 了，效率提升了一大截。
这里需要注意的是，数组的长度为 128，这是基于 ASCII 码的范围设计的。ASCII 码是一种字符编码标准，它将英文字符、数字、标点符号等映射到 0-127 的整数上。
当使用字符 int currValue = values[s.charAt(i)] 作为数组索引时，字符实际上被转换为其对应的 ASCII 值。例如，字符 'A' 对应 ASCII 值 65。
使用 128 大小的数组可以确保直接通过字符的 ASCII 值作为索引来访问数组元素，这样的访问速度更快。
虽然题目中只用到了 7 个罗马字符，但这样可以确保代码的通用性。这是另外一个非常巧妙的地方。
总结
这道题的巧妙之处就在于：对于罗马数字来说，把一个小值放在大值的左边，就是做减法，否则为加法。
剩下的处理就非常简单了。由于罗马数字的数量非常有限，总共就 7 个，仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')，我们也可以通过数组来替代 HashMap，这样的效率会更快一点，虽然 HashMap 的底层也是数组。但毕竟 HashMap 是对数组的一种封装，加上了链表和红黑树，包括扩容等操作，所以效率肯定没有直接使用数组来得高。
这道题目所涉及到的 Java 基础知识有：
力扣链接：https://leetcode.cn/problems/roman-to-integer/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412