13. Roman to Integer

问题描述：
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

分析：
这道题需要了解罗马数字是什么，包含哪些数字。

image.png

1、相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2、小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3、小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4、正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
5、在一个数的上面画一条横线，表示这个数扩大1000倍。

有几条须注意掌握：
1、基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
2、不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
3、V 和X 左边的小数字只能用Ⅰ。
4、L 和C 左边的小数字只能用X。
5、D 和M 左边的小数字只能用C。

思路：

自己的方法：

基本思路就是从右往左读字符串，如果小于当前的number，就用number减掉它，否则加上它。

首先得需要一个函数来将罗马数字转换成对应的阿拉伯数字，或者新建一个字典用来存放对应关系。
根据以上思路，代码如下：

  public int romanToInt(String s) {
        int number = 0;
        for(int i=s.length()-1; i>=0; i--){
            char c = s.charAt(i);
            int n = mapping(c);
            if(n < number) number -= n;
            else number += n;
        }
        return number;  
    }

运行之后发现有错误：

image.png

上面的代码没有考虑到两个一样的数字连着的情况，所以导致加了第一个X之后，本来应该再加X却减了X。

因此，需要对上面的代码进行修改。

    public int romanToInt(String s) {
        int number = mapping(s.charAt(s.length()-1));
        int right = number;
        for(int i=s.length()-2; i>=0; i--){
            int left = mapping(s.charAt(i));
            if(left < right) number -= left;
            else number += right;
            right = left;
        }
        return number;  
    }

加入了一个right变量，记录右边的数字，通过判断左右两个数的大小进行增减操作。

他人的方法：

我是由右向左的，跟右边的数作比较，看了别人的代码是由左向右的，具体的比较方式分为跟左边和右边的数比较两种方式。由此看来，还有其他三种方法。

方法二：

    public int romanToInt(String s) {
        int number = 0;
        for(int i=s.length()-1; i>=0; i--){
            int n= mapping(s.charAt(i));
            if(i==0 || n <= mapping(s.charAt(i-1))) number += n;
            else number += n - 2*mapping(s.charAt(i-1));
        }
        return number;  
    }

从右往左，跟左边数比较，如果小于等于左边数，加上当前数字；如果大于左边数，就加上当前数字减去两倍的左边的数，用来抵消接下来多加上的左边数。

方法三：

    public int romanToInt(String s) {
        int number = 0;
        for(int i=0; i<s.length(); i++){
            int n= mapping(s.charAt(i));
            if(i==0 || n <= mapping(s.charAt(i-1))) number += n;
            else number += n - 2*mapping(s.charAt(i-1));
        }
        return number;  
    }

方法四：

    public int romanToInt(String s) {
        int number = 0;
        for(int i=0; i<s.length(); i++){
            int n= mapping(s.charAt(i));
            if(i==s.length()-1 || n >= mapping(s.charAt(i+1))) number += n;
            else number -= n;
        }
        return number;  
    }

方法三和方法四都是从左至右的，分别与左边和右边的数进行比较。