题目：

Roman to Integer - LeetCode

1.思路

把给定的roman字符串分割成单个字符遍历求和。

如果当前数字比下一个大，那么sum当前值；

如果当前数字比下一个小，那么sum后一个减当前值；

2.知识点

1⃣️对于单个字符的处理，可以使用Character类（unicode 2字节）来处理更生内存。

2⃣️new 一个初始化的map，需要实例化时指定范型，然后调用HashMap内部的put方法初始化。

3⃣️在循环中使用continue是损耗循环性能的（小list？）。

4⃣️对于基本数据类型在循环中声明或者循环外效果差不多。

5⃣️把map改为switch效率更高（小数据量，大量的话map更高，因为有JIT优化map）。

Java性能测试的困惑：switch和map的性能比较

3.代码如下：

package com.eironn.leetcode;

import java.util.HashMap;
import java.util.Map;

public class RomanToInteger {

    public int romanToInt(String roman) {
        Map<Character, Integer> map = new HashMap<Character, Integer>() {
            {
                put('I', 1);
                put('V', 5);
                put('X', 10);
                put('L', 50);
                put('C', 100);
                put('D', 500);
                put('M', 1000);
            }
        };
        char[] chars = roman.toCharArray();
        int resp = 0;
        int addValue;
        for (int i = 0; i < chars.length; i++) {
            if (i + 1 < chars.length) {
                if (map.get(chars[i]) >= map.get(chars[i + 1])) {
                    addValue = map.get(chars[i]);
                } else {
                    addValue = map.get(chars[i + 1]) - map.get(chars[i]);
                    i++;
                }
            } else {
                addValue = map.get(chars[i]);
            }
            resp += addValue;
        }
        return resp;
    }
}

4.第二种思路

逆序整个字符串，从右向左，加上每个字符串（如果下个字符串小于当前，加一个负），好处是可以只算加法。

class Solution {

    public int romanToInt(String s) {
        int sum = getValue(s.charAt(s.length()-1));

        for(int i = s.length() - 2; i >= 0; --i) {
            int cVal = getValue(s.charAt(i));
            int pVal = getValue(s.charAt(i+1));
            sum += cVal >= pVal ? cVal : cVal*(-1);
        }

        return sum;
    }

    public int getValue(char c) {
        switch (c) {
            case 'M':
                return 1000;
            case 'D':
                return 500;
            case 'C':
                return 100;
            case 'L':
                return 50;
            case 'X' :
                return 10;
            case 'V':
                return 5;
            case 'I':
                return 1;
        }
        return 0;
    }
}

5.另一种思路

先替换特殊字符（4,9,40,90），再替换普通字符(1,5,10,50)

比较慢

public class SolutionMe4 {

    /**
     * 29 ms
     * 先替换特殊的4，9，40，90，再替换普通的。
     *
     * @param roman
     * @return
     */
    public int romanToInt(String roman) {
        int resp = 0;
        Map<String, Integer> map = new LinkedHashMap<String, Integer>() {
            {
                put("IV", 4);
                put("CM", 900);
                put("XL", 40);
                put("XC", 90);
                put("CD", 400);
                put("IX", 9);
                put("I", 1);
                put("V", 5);
                put("X", 10);
                put("L", 50);
                put("C", 100);
                put("D", 500);
                put("M", 1000);
            }
        };
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            while (roman.contains(key)) {
                resp += value;
                roman = roman.replaceFirst(key, "");
            }
        }
        return resp;
    }
}