【LeetCodeJava】13.罗马数字转整数（简单）

1. 题目描述

2. 解题思路

这道题目的第一个思路就是先把输入的字符串转换成字符数组&＃xff0c;对字符数组进行遍历&＃xff0c;利用switch进行对应的罗马字符判断&＃xff0c;然后判断特殊情况的时候向后看多一位。这种方法简单直接&＃xff0c;应该大部分都能想得出来。但是运行了一下发现&＃xff0c;嗯…问题是能解决的&＃xff0c;但是效率不够高。

经过一番思考发现&＃xff0c;每一次判断特殊情况都需要向后看多一位&＃xff0c;影响效率&＃xff0c;转变一下方式&＃xff0c;我们可以每读一个字符就记下来&＃xff0c;每次判断时利用上一次记下来的值进行比较&＃xff0c;那就可以省去向后看多一位这个动作&＃xff0c;一定程度上其实是属于空间换时间的操作&＃xff08;多存一个变量&＃xff0c;少查一次&＃xff09;&＃xff0c;这种方法可以通过switch或hashmap实现。

做完以上两种尝试过后结果还不错&＃xff0c;看了一眼题解能有什么奇招&＃xff0c;发现还可以进行字符串替换&＃xff0c;即把特殊情况的字符串都替换成自定义字符&＃xff0c;方便后续进行运算&＃xff0c;这个方法有点意思&＃xff0c;但在效率上会稍微逊色。

3. 代码实现

3.1 向后多看一位&＃xff08;switch&＃xff09;

public int romanToInt(String s) {char[] chars &＃61; s.toCharArray();int sum &＃61; 0;int length &＃61; chars.length;for (int i &＃61; 0; i < length; i&＃43;&＃43;) {switch (chars[i]) {case &＃39;I&＃39;:try {if (chars[i &＃43; 1] &＃61;&＃61; &＃39;V&＃39; || chars[i &＃43; 1] &＃61;&＃61; &＃39;X&＃39;) {sum &＃61; sum - 1;} else {sum &＃61; sum &＃43; 1;}} catch (Exception e) {return sum &＃43; 1;}break;case &＃39;X&＃39;:try {if (chars[i &＃43; 1] &＃61;&＃61; &＃39;L&＃39; || chars[i &＃43; 1] &＃61;&＃61; &＃39;C&＃39;) {sum &＃61; sum - 10;} else {sum &＃61; sum &＃43; 10;}} catch (Exception e) {return sum &＃43; 10;}break;case &＃39;C&＃39;:try {if (chars[i &＃43; 1] &＃61;&＃61; &＃39;D&＃39; || chars[i &＃43; 1] &＃61;&＃61; &＃39;M&＃39;) {sum &＃61; sum - 100;} else {sum &＃61; sum &＃43; 100;}} catch (Exception e) {return sum &＃43; 100;}break;case &＃39;V&＃39;:sum &＃61; sum &＃43; 5;break;case &＃39;L&＃39;:sum &＃61; sum &＃43; 50;break;case &＃39;D&＃39;:sum &＃61; sum &＃43; 500;break;case &＃39;M&＃39;:sum &＃61; sum &＃43; 1000;break;}}return sum;}


3.2 记住前一位数&＃xff08;hashmap&＃xff09;

public int romanToInt(String s) {int sum &＃61; 0;char[] chars &＃61; s.toCharArray();HashMap<Character, Integer> changeMap &＃61; new HashMap<>();changeMap.put(&＃39;I&＃39;, 1);changeMap.put(&＃39;V&＃39;, 5);changeMap.put(&＃39;X&＃39;, 10);changeMap.put(&＃39;L&＃39;, 50);changeMap.put(&＃39;C&＃39;, 100);changeMap.put(&＃39;D&＃39;, 500);changeMap.put(&＃39;M&＃39;, 1000);int old &＃61; 1001;for (char aChar : chars) {Integer integer &＃61; changeMap.get(aChar);if (old < integer) {sum -&＃61; 2 * old;}sum &＃43;&＃61; integer;old &＃61; integer;}return sum;}


3.3 记住前一位数&＃xff08;switch&＃xff09;

public int romanToInt(String s) {int sum &＃61; 0;char[] chars &＃61; s.toCharArray();int old &＃61; 1001;int integer &＃61; 0;for (char aChar : chars) {switch (aChar) {case &＃39;I&＃39;:integer &＃61; 1;break;case &＃39;X&＃39;:integer &＃61; 10;break;case &＃39;C&＃39;:integer &＃61; 100;break;case &＃39;V&＃39;:integer &＃61; 5;break;case &＃39;L&＃39;:integer &＃61; 50;break;case &＃39;D&＃39;:integer &＃61; 500;break;case &＃39;M&＃39;:integer &＃61; 1000;break;}if (old < integer) {sum -&＃61; 2 * old;}sum &＃43;&＃61; integer;old &＃61; integer;}return sum;}


我所尝试的四种算法当中这种算法是最优的结果&＃xff1a;

3.4 替换输入字符串&＃xff08;switch&＃xff09;

public int romanToInt(String s) {int sum &＃61; 0;s &＃61; s.replace("IV", "a");s &＃61; s.replace("IX", "b");s &＃61; s.replace("XL", "c");s &＃61; s.replace("XC", "d");s &＃61; s.replace("CD", "e");s &＃61; s.replace("CM", "f");char[] chars &＃61; s.toCharArray();for (char aChar : chars) {switch (aChar) {case &＃39;I&＃39;:sum &＃43;&＃61; 1;break;case &＃39;X&＃39;:sum &＃43;&＃61; 10;break;case &＃39;C&＃39;:sum &＃43;&＃61; 100;break;case &＃39;V&＃39;:sum &＃43;&＃61; 5;break;case &＃39;L&＃39;:sum &＃43;&＃61; 50;break;case &＃39;D&＃39;:sum &＃43;&＃61; 500;break;case &＃39;M&＃39;:sum &＃43;&＃61; 1000;break;case &＃39;a&＃39;:sum &＃43;&＃61; 4;break;case &＃39;b&＃39;:sum &＃43;&＃61; 9;break;case &＃39;c&＃39;:sum &＃43;&＃61; 40;break;case &＃39;d&＃39;:sum &＃43;&＃61; 90;break;case &＃39;e&＃39;:sum &＃43;&＃61; 400;break;case &＃39;f&＃39;:sum &＃43;&＃61; 900;break;}}return sum;}


3.5 对比

显然&＃xff0c;采用哈希表的代码看上去更加优雅&＃xff0c;但需要占用额外的存储空间&＃xff0c;并且比switch略慢一点。