JAVA练习368- 罗马数字转整数

题目概览罗马数字包含以下七种字符:IVXLCD和M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如 罗马数字2写做II即为两个并列的 1 。12写做XII即为XII。27写做XXVII, 即为XXVII。通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做IIII而是IV。数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地数字 9 表示为IX。这个特殊的规则只适用于以下六种情况I可以放在V(5) 和X(10) 的左边来表示 4 和 9。X可以放在L(50) 和C(100) 的左边来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边来表示 400 和 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.提示1 s.length 15s仅含字符(I, V, X, L, C, D, M)题目数据保证s是一个有效的罗马数字且表示整数在范围[1, 3999]内题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况。IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX 。关于罗马数字的详尽书写规则可以参考 罗马数字 - 百度百科。来源13. 罗马数字转整数 - 力扣LeetCode解题分析方法模拟核心思路从左到右遍历罗马数字字符串比较相邻两个字符对应的数值。如果当前字符的值小于下一个字符的值则减去当前值否则加上当前值。最后加上最后一个字符的值。算法步骤建立罗马字符到数值的映射表HashMap。初始化结果变量result 0。遍历字符串的前n-1个字符i从 0 到n-2获取当前字符s.charAt(i)对应的值val。比较val与下一个字符s.charAt(i1)对应的值若val map.get(s.charAt(i1))说明是特殊情况如 IV、IX 等则result - val。否则result val。循环结束后加上最后一个字符的值result map.get(s.charAt(n-1))。返回result。为什么这样可行罗马数字的规则是一般情况下数字从左到右按值递减排列大的在左小的在右直接相加即可。但当小的数字出现在大的数字左边时表示减法组合如 IV 5 - 1 4。我们的遍历策略正好捕捉了这一规则对于正常情况如 VI 5 1当前值 ≥ 下一个值直接加。对于特殊情况如 IV 1 在 5 左边当前值 下一个值则减去当前值相当于先减 1后面再加 5。最后单独处理最后一个字符是因为循环只比较到倒数第二个字符最后一个字符没有下一个字符可比较直接加上即可。时间复杂度O(n)其中 n 是字符串长度。只需一次遍历。空间复杂度O(1)。虽然使用了 HashMap但映射表大小固定7 个字符与输入规模无关。class Solution { // 建立罗马字符到数值的映射 MapCharacter, Integer map new HashMapCharacter, Integer() {{ put(I, 1); put(V, 5); put(X, 10); put(L, 50); put(C, 100); put(D, 500); put(M, 1000); }}; public int romanToInt(String s) { int result 0; int n s.length(); // 遍历前 n-1 个字符 for (int i 0; i n - 1; i) { int val map.get(s.charAt(i)); // 如果当前值小于下一个值说明是减法组合如 IV、IX if (val map.get(s.charAt(i 1))) { result - val; } else { result val; } } // 加上最后一个字符的值 result map.get(s.charAt(n - 1)); return result; } }示例解析以s MCMXCIV为例M (1000) C (100) → 1000C (100) M (1000) → -100M (1000) X (10) → 1000X (10) C (100) → -10C (100) I (1) → 100I (1) V (5) → -1最后加上 V (5) → 5总和1000 - 100 1000 - 10 100 - 1 5 1994