leetCode 13. Roman to Integer 字符串

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.

补充：罗马数字

罗马数字共有七个，即I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。按照下面的规则可以表示任意正整数。

重复数次：一个罗马数字重复几次，就表示这个数的几倍。 

右加左减：在一个较大的罗马数字的右边记上一个较小的罗马数字，表示大数字加小数字。在一个较大的数字的左边记上一个较小的罗马数字，表示大数字减小数字。但是，左减不能跨越等级。比如，99不可以用IC表示，用XCIX表示。 

加线乘千：在一个罗马数字的上方加上一条横线或者在右下方写M，表示将这个数字乘以1000，即是原数的1000倍。同理，如果上方有两条横线，即是原数的1000000倍。 

单位限制：同样单位只能出现3次，如40不能表示为XXXX，而要表示为XL。

思路：

将字符串分为3部分，left，mid，right。

获取当前字符串的最大单位m。记录位置，字符。

获取最大单位连续出现的次数n。

通过递归，结果为m*n - 左边 + 右边。

代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

<code>int</code> <code>romanToInt(string s) {</code>

<code>    </code><code>if</code> <code>(s.size() == 0)</code>

<code>        </code><code>return</code> <code>0;</code>

<code>    </code><code>string left, right;</code>

<code>    </code><code>map&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt; romanMap;</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'I'</code><code>, 1));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'V'</code><code>, 5));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'X'</code><code>, 10));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'L'</code><code>, 50));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'C'</code><code>, 100));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'D'</code><code>, 500));</code>

<code>    </code><code>romanMap.insert(pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt;(</code><code>'M'</code><code>, 1000));</code>

<code>    </code><code>int</code> <code>maxGrade = 0; </code><code>//最高级</code>

<code>    </code><code>char</code> <code>maxChar = </code><code>'\0'</code><code>;</code>

<code>    </code><code>int</code> <code>maxGrades = 0;</code><code>//最高级次数</code>

<code>    </code><code>int</code> <code>maxGradePos = 0; </code><code>//最高级位置</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; s.size(); i++)</code><code>//获取最高级字符，最高级位置</code>

<code>    </code><code>{</code>

<code>        </code><code>if</code> <code>(romanMap[s[i]] &gt; maxGrade)</code>

<code>        </code><code>{</code>

<code>            </code><code>maxGrade = romanMap[s[i]];</code>

<code>            </code><code>maxChar = s[i];</code>

<code>            </code><code>maxGradePos = i;</code>

<code>        </code><code>}</code>

<code>    </code><code>}</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = maxGradePos; i &lt; s.size(); i++)</code><code>//获取最高级连续次数</code>

<code>        </code><code>if</code> <code>(s[i] == maxChar)</code>

<code>            </code><code>maxGrades++;</code>

<code>        </code><code>else</code>

<code>            </code><code>break</code><code>;</code>

<code>    </code><code>left = s.substr(0, maxGradePos);</code>

<code>    </code><code>right = s.substr(maxGradePos + maxGrades);</code>

<code>    </code><code>return</code> <code>maxGrades * maxGrade - romanToInt(left) + romanToInt(right);</code>

<code>}</code>

参考他人做法：

参考网址：http://blog.csdn.net/feliciafay/article/details/17259547

观察到罗马数字和Integer的转换的小规律是：

IV = 5 -  1 =  (-1) + 5 = 4

VI = 5 + 1 = 5 + 1 = 6

I在V前面，由于I比V小，所以I被解释为负数。

V在I后面，由于V比I大，所以V给解释为整数。

继续看几个例子。

VII = 5 + 1 + 1 = 7

IX = (-1) + 10 = 9

所以，可以一次把输入字符串扫描一遍，从第一个字符开始，到最后一个字符为止，一次比较当前字符a和当前字符的下一个字符b。如果a&lt; b ，解释为 b - a,否则如果a &gt;= b， 解释为a + b。 实际上，由于每次总是比较2个相邻的字符，所以是下标是从0开始，到inputstring.length()-2结束。

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>romanToInt(string s) {</code>

<code>        </code><code>int</code> <code>sum = 0;  </code>

<code>        </code><code>int</code> <code>start = 0;  </code>

<code>  </code> 

<code>        </code><code>char</code> <code>char_arr[] = {</code><code>'I'</code><code>, </code><code>'V'</code><code>, </code><code>'X'</code><code>, </code><code>'L'</code><code>, </code><code>'C'</code><code>, </code><code>'D'</code><code>, </code><code>'M'</code><code>};  </code>

<code>        </code><code>int</code> <code>int_arr[] = {1, 5, 10, 50, 100, 500, 1000};  </code>

<code>        </code><code>std::map&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt; roman_map;  </code>

<code>        </code><code>int</code> <code>map_len = </code><code>sizeof</code><code>(char_arr)/</code><code>sizeof</code><code>(</code><code>char</code><code>);   </code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i&lt; map_len; ++i)   </code>

<code>            </code><code>roman_map.insert(std::pair&lt;</code><code>char</code><code>, </code><code>int</code><code>&gt; (char_arr[i], int_arr[i]));  </code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; s.length() - 1; ++i) {  </code>

<code>            </code><code>if</code> <code>(roman_map[s[i]]&gt;=roman_map[s[i + 1]])  </code>

<code>                </code><code>sum += roman_map[s[i]];  </code>

<code>            </code><code>else</code>  

<code>                </code><code>sum -= roman_map[s[i]];  </code>

<code>        </code><code>}  </code>

<code>        </code><code>sum += roman_map[s[s.length()-1]];  </code>

<code>        </code><code>return</code> <code>sum;  </code>

<code>};</code>

<code></code>

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1836563