Roman to Integer

Easy
keyword: Pattern
类似: Gray, Digit Counts, rotate graph, Max Tree, Triangle Sum,

羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。按照下述的規則可以表示任意正整數。需要注意的是罗马数字中没有“0”，與進位制無關。一般認為羅馬數字只用來記數，而不作演算。

重複數次：一個羅馬數字重複幾次，就表示這個數的幾倍。

右加左減：

在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。

在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字减小數字。

左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV

思考

这种就是通过找到Pattern来解决问题, 类似的有Gray code, Digit Counts, rotate graph. 都是理解题意, 找到规律, 然后解决问题.
同时也可以发现反过来解决比正向更好解决, 这就类似Max Tree, Triangle Sum, 乃至于所有top-down/bottom-up的recursion.

idea 1: 正向loop

既然题目说的左小就减小: IV = 5-1, 右小就加小: VI = 5 + 1. 那么从头过一遍, 比较前一个数和当前的数, 若前小就相减, 若前大就相加. 注意这里已经和题意有点区别, 但是是等价的, 因为这样才好loop解决.
正如: maples7分析的: 由于result holder在i的时候, 已经加入了s[i-1]了, 所以相减的时候要减去之前加了的s[i-1]. 对 s[i-2] 分情况讨论便知.
下面举2个例子:
1. 简单的: MMXII, 由于是递减的, 所以都是第一种情况, 即大的罗马数字右边接一个小的, 所以加就好了. 即M+M+X+I+I = 1000 + 1000 + 10 + 1 + 1 = 2012
2. 来一个综合的例子:
代码如下: MCMXCVI. 注意有CM, XC. 这些是左边接小的罗马数字, 所以相减, 即M+(CM)+(XC)+V+I = M + (M-C) + (C-X) + V + I = 1000 + (1000-100) + (100-10) + 5 + 1 = 1996.

public int romanToIntPosOrd(String s) {
    if (s == null || s.length() == 0) return 0;
    Map<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 len = s.length();
    char[] Arr = s.toCharArray();
    int res = map.get(Arr[0]);
    for (int i = 1; i < len; ++i) {
      if (map.get(Arr[i - 1]) <= map.get(Arr[i])) {
        res += map.get(Arr[i]) - 2 * map.get(Arr[i-1]);  // 注意此时要剪掉i-1的时候加上的Arr[i-1]
      } else {
        res += map.get(Arr[i]);  // 此时加上Arr[i].
      }
    }
    return res;
}

idea 2: 反向looping

由于正向loop的时候, 会有出现: 先是加了C, 结果发现下一个是M, 从而应该是CM组合后再加, 即加上M-C, 所以第一次加多了一次C, 从而出现了补救/修正的过程, 即: map.get(Arr[i]) - 2 * map.get(Arr[i-1]).
可以更好的解决问题吗?
一般来说: 大部分问题都可以正的/烦得解决. 所以看看反过来会怎样: 同样是以包含2种规则的例子: MCMXCVI为例: 从后向前是: I + V + C - X + M - C + M, 这不是很完美吗? 不用修正, 只要看大小来确定是加/减.
代码如下

public int romanToIntPosOrd(String s) {
    if (s == null || s.length() == 0) return 0;
    Map<Character, Integer> map = new HashMap<>();  // map过程如上, 就不重复了.
    int len = s.length();
    char[] Arr = s.toCharArray();
    int res = map.get(Arr[len-1]);
    for (int i = len-2; i >= 0; i--) {
      if (map.get(Arr[i + 1]) <= map.get(Arr[i])) {
        res += map.get(Arr[i]);  // 比正向漂亮多了
      } else {
        res -= map.get(Arr[i]); 
      }
    }
    return res;
}