ARTS leetcode5 Roman to Integer

一时失言乱红尘 2022-02-18 08:19 136阅读 0赞

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
    
    Symbol       Value
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000
    For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
    
    Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
    
    I can be placed before V (5) and X (10) to make 4 and 9. 
    X can be placed before L (50) and C (100) to make 40 and 90. 
    C can be placed before D (500) and M (1000) to make 400 and 900.
    Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
    
    Example 1:
    
    Input: "III"
    Output: 3
    Example 2:
    
    Input: "IV"
    Output: 4
    Example 3:
    
    Input: "IX"
    Output: 9
    Example 4:
    
    Input: "LVIII"
    Output: 58
    Explanation: L = 50, V= 5, III = 3.
    Example 5:
    
    Input: "MCMXCIV"
    Output: 1994
    Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

题目意思就是：  
（1）每种罗马字符代表一种阿拉伯数字，  
（2）一些罗马字符的组合也可以代表一些阿拉伯的数字，  
（3）有一些特殊的例子，比如4,9,40,90,400,900等罗马表示方法，  
（4）而且一般罗马字符组合的表示的数值从左到右数值是从大到小的规律。

我的思路：  
把给定的罗马字符串一个字符一个字符进行匹配上面给的几种，如果匹配到就把其映射到的值相加，此时有个特殊例子，就是题目意思中的(3)，这种情况下，小值的字符在大值的字符后面，结果就后面大值的字符减掉前面小值的字符。比如IV是4，也就是V=5 I=1,结果就是5-1，所以在循环的时候需要比较一下前后两个字符的值的大小，情况①如果前者比后者大，那么就直接把前者的值进行累加继续循环，情况②否则就需要把后者的值减掉前者的值之后在进行累加，需要特别注意的是，这里情况①，步长是1，情况②因为你这个值是两个元素之差，所以进行下一次运算的时候，步长就变为2了，否则会出现奇怪的结果。

伪代码：

1.罗马映射关系用map封装map.put(character,integer);  
2.s不为空时，将字符串转为字符数组  
3.对字符数组进行循环，分两种情况：  
(1)前者的值大于后者值，则用result进行累加,步长为1  
(2)前者值小于后者值，则用result累加(后者值-前者值)，步长为2  
4.最后返回result

我的思路代码实现：

class Solution {
        public 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 = 0;
            if(s!=null && s.length()>0){
                char[] ch = s.toCharArray();
                int len = ch.length;
                for(int i=0;i<len;){
                    if(map.get(ch[i]) >= map.get(i+1>=len-1?ch[len-1]:ch[i+1])){
                        result += map.get(ch[i]);
                        i++;
                    }else{
                        result +=(map.get(i+1>=len-1?ch[len-1]:ch[i+1]) - map.get(ch[i]));
                        i+=2;
                    }
                }
            }
            return  result; 
        }
    }

Runtime: 6 ms, faster than 99.61% of Java online submissions for Roman to Integer.
    Memory Usage: 37.4 MB, less than 34.56% of Java online submissions for Roman to Integer.

下面分享两种其他人的做法，代码是从leetcode，思路基本是一样的，只是实现不同，略微有些区别，下面是代码分享：

code1:

class Solution {
        public int romanToInt(String s) {
         int num = 0;
            int l = s.length();
            int last = 1000;
            for (int i = 0; i < l; i++){
                int v = getValue(s.charAt(i));
                if (v > last) num = num - last * 2;
                num = num + v;
                last = v;
            }
            return num;
        }
        private int getValue(char c){
            switch(c){
                case 'I' : return 1;
                case 'V' : return 5;
                case 'X' : return 10;
                case 'L' : return 50;
                case 'C' : return 100;
                case 'D' : return 500;
                case 'M' : return 1000;
                default : return 0;
            }
        }
    }

Runtime: 3 ms, faster than 100.00% of Java online submissions for Roman to Integer.
    Memory Usage: 37.3 MB, less than 35.04% of Java online submissions for Roman to Integer.

这段代码中用了switch语句，核心代码是for循环里面那部分。

code2:

class Solution {
        public int romanToInt(String s) {
           int[] a = new int[26];
            a['I' - 'A'] = 1;
            a['V' - 'A'] = 5;
            a['X' - 'A'] = 10;
            a['L' - 'A'] = 50;
            a['C' - 'A'] = 100;
            a['D' - 'A'] = 500;
            a['M' - 'A'] = 1000;
            char prev = 'A';
            int sum = 0;
            for(char b : s.toCharArray()) {
                if(a[b - 'A'] > a[prev - 'A']) {
                    sum = sum - 2 * a[prev - 'A'];
                }
                sum = sum + a[b - 'A'];
                prev = b;
            }
            return sum;
            }
    }

Runtime: 3 ms, faster than 100.00% of Java online submissions for Roman to Integer.
    Memory Usage: 37.3 MB, less than 35.04% of Java online submissions for Roman to Integer.

这个也是循环了一次，但是特殊之处在于，他利用数组数据结构，然后将数组元素按照字母表26个元素一样排列。思想还是前后两者需要比较一下。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220218/4cac080add474b55863b7851b42e7358.png