力扣面试经典算法150题：罗马数字转整数

罗马数字转整数

今天的题目是力扣面试经典150题中的数组的简单题: 罗马数字转整数

题目链接：https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

将一个罗马数字转换成相应的整数。输入是一个有效的罗马数字字符串，输出是对应的整数值。
罗马数字包含以下七种字符: I, V, X, L, C, D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

示例:
- 输入:
  “III”
- 输出:
  3
- 输入:
  “IV”
- 输出:
  4
- 输入:
  “IX”
- 输出:
  9
- 输入:
  “LVIII”
- 输出:
  58
- 输入:
  “MCMXCIV”
- 输出:
  1994

题目分析

罗马数字的转换规则：正常情况下，字符代表的数值相加得到最终结果；特殊情况下，如果较小的数字出现在较大的数字前面，则从较大的数字中减去较小的数字。

简单分析一下：

以5为分隔时(1-5,5-10,实际间隔是4)，间隔在1-3时使用I叠加，间隔为4时在下级符号V/X前加I。
以50为分隔时(10-50,50-100,实际间隔是40)，间隔在10-30使用X叠加，间隔为40时在下级符号L/C前加X。
以500为分隔时(100-500,500-1000,实际间隔是400)，间隔在100-300使用C叠加，间隔为400时在下级符号D/M前加C。

针对这种情况，我们可以总结一下，如果当前位罗马字符对应的值小于下一位罗马字符对应的值，那么就应该先减去当前位罗马字符，如果大于或者没有下一位罗马字符，则说明符合正常的累加规则，直接相加即可。比如IV = -10 + 50，更多的例子大家可以往后举例并归纳。

实际通过大量例子找规律，再使用代码实现这个规律就是在编写算法，就像我们高中学的数列一下。

个人理解不喜吻喷。

最后由于题目只给到1000的对应罗马值，输入的罗马字符的值应该限制在3999以内。

解题思路

这个题目没有想到特别的算法来解答，目前就考虑暴力破解。

暴力破解的思路如下：

使用哈希表存储罗马数字及其对应的整数值。
从左到右遍历字符串，检查当前字符与下一个字符的值的大小。
如果当前字符的值小于下一个字符的值，则从结果中减去当前字符的值；否则，加上当前字符的值。

最终得到的整数值即为结果。

实际算法代码

根据以上分析，我们可以写出以下代码：

import java.util.HashMap;
import java.util.Map;public class RomanToInteger {public static void main(String[] args) {RomanToInteger solution = new RomanToInteger();// 示例数据String romanNumeral = "MCMXCIV";// 调用转换方法int integerResult = solution.romanToInt(romanNumeral);// 输出结果System.out.println("The integer value of the Roman numeral " + romanNumeral + " is: " + integerResult);}/*** 将罗马数字转换为整数** @param s 输入的罗马数字字符串* @return 对应的整数值*/public int romanToInt(String s) {Map<Character, Integer> romanValues = new HashMap<>();romanValues.put('I', 1);romanValues.put('V', 5);romanValues.put('X', 10);romanValues.put('L', 50);romanValues.put('C', 100);romanValues.put('D', 500);romanValues.put('M', 1000);int result = 0;for (int i = 0; i < s.length(); i++) {char currentChar = s.charAt(i);int currentValue = romanValues.get(currentChar);if (i + 1 < s.length() && currentValue < romanValues.get(s.charAt(i + 1))) {result -= currentValue;} else {result += currentValue;}}return result;}
}