13. Roman to Integer

罗马数字

基本字符 I V X L C D M
对应阿拉伯数字 1 5 10 50 100 500 1000

计数规则：

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
2. 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
3. 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4
4. 正常使用时，连续的数字重复不得超过三次
5. 在一个数的上面画横线，表示这个数扩大1000倍（本题只考虑3999以内的数，所以用不到这条规则）

其次，罗马数字转阿拉伯数字规则（仅限于3999以内）：

首先，从前向后遍历罗马数字，加上所有字母对应的数字，得到sum；
然后，如果某个数比后一个数小，则在sum中减去前一个数的两倍
（减掉 之前加上的数字，再减去自己）

字符串版本

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int len = s.length();
        // how to convert a STRING to a CHARACTER ARRAY
        char c[] = s.toCharArray();  // HERE!!!
        // for me, i always works as an INDEX
        for (int i = 0; i < len; i++){
            if (c[i] == 'I') {sum += 1;}
            if (c[i] == 'V') {sum += 5;}
            if (c[i] == 'X') {sum += 10;}
            if (c[i] == 'L') {sum += 50;}
            if (c[i] == 'C') {sum += 100;}
            if (c[i] == 'D') {sum += 500;}
            if (c[i] == 'M') {sum += 1000;}
        }
        // Check the inverse order; using s.indexOf("")
        // and subtract the number
        // NOTICE that: we won't subtract 5*10^k, 
        // because we can get that # by adding rather than subtract.
        if (s.indexOf("IV") != -1) {sum -= 2;}
        if (s.indexOf("IX") != -1) {sum -= 2;}
        if (s.indexOf("XL") != -1) {sum -= 20;}
        if (s.indexOf("XC") != -1) {sum -= 20;}
        if (s.indexOf("CD") != -1) {sum -= 200;}
        if (s.indexOf("CM") != -1) {sum -= 200;}
        return sum;



    }
}

处理字符串的方法

通常处理字符串的方法有两种：

• char c[] = s.toCharArray();
• char c = s.charAt(i)
  where, i is the index.

另外一个直接按照罗马数字定义的方法：
only scan the string once.
从后往前扫：较小数字的加法，总是在大数字的后面。
数字大到一定值后，位于前部的小数字进行的是减法。

public static int romanToInt(String s) {
    int res = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        char c = s.charAt(i);
        switch (c) {
        case 'I':
            res += (res >= 5 ? -1 : 1);
            break;
        case 'V':
            res += 5;
            break;
        case 'X':
            res += 10 * (res >= 50 ? -1 : 1);
            break;
        case 'L':
            res += 50;
            break;
        case 'C':
            res += 100 * (res >= 500 ? -1 : 1);
            break;
        case 'D':
            res += 500;
            break;
        case 'M':
            res += 1000;
            break;
        }
    }
    return res;
}

Map：

    public static int romanToInt(String s) {
    if (s == null || s.length() == 0)
        return -1;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    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 len = s.length(), result = map.get(s.charAt(len - 1));
    for (int i = len - 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;
}