:-: 6.2 罗马数字转整数 * * * * * **题干：** 罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。 ~~~ 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 ~~~ 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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 到 3999 的范围内。 示例 1: ~~~ 输入: "III" 输出: 3 ~~~ 示例 2: ~~~ 输入: "IV" 输出: 4 ~~~ 示例 3: ~~~ 输入: "IX" 输出: 9 ~~~ 示例 4: ~~~ 输入: "LVIII" 输出: 58 解释: C = 100, L = 50, XXX = 30, III = 3. ~~~ 示例 5: ~~~ 输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4. ~~~ **题目分析：** 通过题目来看，我们只要把字符串转换为字符类型，然后再转换为对应的整数即可，但是还有六种特殊情况（IV、IX、XL、XC、CD、CM）是两个结合在一起计算的，这就需要当我们检测到前一个字符是（I、X、C）这三种之一，判断后面是不是（V、X、L、C、D、M）这六种所能结合的字符，我们再分析发现，如果我们输入的罗马数字是标准罗马数字，我们只要考虑当前一个字符所对应的整数小于后一个字符对应的整数（就用后一个字符对应的整数减去前一个字符所对应的整数即可）或者反向判断当前一个字符所对应的整数大于后一个字符对应的整数（就用前一个字符对应的整数减去后一个字符所对应的整数即可）。 **新手有可能遇到的解题思路陷阱：** 考虑过多，我们不必在意那些非标准的罗马数字的输入，或者没有考虑那六种特殊情况，还有边界值的处理（最后一项可能漏掉或者直接数组越界）。 **解题思路分析以及代码实现：** 第一种思路：精确判断，（IV、IX、XL、XC、CD、CM）。 第一种思路代码： ~~~ public static int romanToInt(String s) { char[] ch = s.toCharArray(); int result = 0; for (int i = 0; i < ch.length; ++i) { switch (ch[i]) { case 'M': result += 1000; break; case 'D': result += 500; break; case 'L': result += 50; break; case 'V': result += 5; break; case 'I': if (i + 1 < ch.length && (ch[i + 1] == 'V' || ch[i + 1] == 'X')) { result -= 1; } else { result += 1; } break; case 'X': if (i + 1 < ch.length && (ch[i + 1] == 'L' || ch[i + 1] == 'C')) { result -= 10; } else { result += 10; } break; case 'C': if (i + 1 < ch.length && (ch[i + 1] == 'D' || ch[i + 1] == 'M')) { result -= 100; } else { result += 100; } break; } } return result; } ~~~ 异曲同工： ~~~ public static int romanToInt(String s) { char[] c = s.toCharArray(); int res = 0; for (int i = s.length() - 1; i >= 0; i--) { switch (c[i]) { case 'I': res += (res >= 5 ? -1 : 1); break; case 'V': res += 5; break; case 'X': res += (res >= 50 ? -10 : 10); break; case 'L': res += 50; break; case 'C': res += (res >= 500 ? -100 : 100); break; case 'D': res += 500; break; case 'M': res += 1000; break; } } return res; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：正向模糊判断。 第二种思路代码： ~~~ public static int romanToInt(String s) { HashMap<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int length = s.length(); int result = 0; int i = 0; while (i < length) { if (i < length - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) { result += map.get(s.charAt(i + 1)) - map.get(s.charAt(i)); i += 2; } else { result += map.get(s.charAt(i)); i++; } } return result; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路：反向模糊判断。 第二种思路代码： ~~~ public static int romanToInt(String s) { HashMap<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int result = map.get(s.charAt(s.length() - 1)); for (int i = s.length() - 2; i >= 0; i--) { if (map.get(s.charAt(i)) >= map.get(s.charAt(i + 1))) { result += map.get(s.charAt(i)); } else { result -= map.get(s.charAt(i)); } } return result; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**