13. 罗马数字转整数 Leetcode

Posted on In Views: Disqus:
LeetCode刷题系列。

描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

示例 3:

1
2
输入: "IX"
输出: 9

示例 4:

1
2
3
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：13. Roman to Integer

解题思路

以下内容来自维基百科：

罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”，与进位制无关。一般认为罗马数字只用来记数，而不作演算。

重复数次：一个罗马数字重复几次，就表示这个数的几倍。
右加左减：
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
但是，左减时不可跨越一个位值。比如，99不可以用IC（100−1100−1{\displaystyle 100-1}100-1）表示，而是用XCIX（[100−10]+[10−1][100−10]+[10−1]{\displaystyle [100-10]+[10-1]}[100-10]+[10-1]）表示。（等同于阿拉伯数字每位数字分别表示。）
左减数字必须为一位，比如8写成VIII，而非IIX。
右加数字不可连续超过三位，比如14写成XIV，而非XIIII。（见下方“数码限制”一项。）
加线乘千：
在罗马数字的上方加上一条横线或者加上下标的M，表示将这个数乘以1000，即是原数的1000倍。
同理，如果上方有两条横线，即是原数的1000000（1000210002{\displaystyle 1000^{2} }1000^{ {2} }）倍。
数码限制：
同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。
例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV。

有几条须注意掌握：

  • 基本数字I、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
  • 不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
  • V 和X 左边的小数字只能用Ⅰ。
  • L 和C 左边的小数字只能用X。
  • D 和M 左边的小数字只能用C。

本题简单就简单在，没有让我们来验证输入字符串是不是有效的罗马数字字符串，我们用一个map函数来将罗马数字的字母转化为对应的整数值，因为输入的一定是罗马数字，那么我们只要考虑两种情况即可：

  • 如果当前数字是最后一个数字，或者之后的数字比它小的化，则加上当前数字
  • 其它情况则减去这个数字，这个其它情况主要保护以下六种情况：
    • V左边是I
    • X左边是I
    • L左边是X
    • C左边是X
    • D左边是C
    • M左边是C

具体代码如下：

代码

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
//构造map函数
int map(char s)
{
    switch(s)
    {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}



int romanToInt(char * s)
{
    int result = 0;
    int length = strlen(s);
    
    for(int i = 0; i < length; i++)
    {
        if(i == length -1 || map(s[i + 1]) <= map(s[i])) //情况一：当前数字是最后一个数字，或者之后的数字比它小的化，则加上当前数字
            
            result += map(s[i]);
        
        else                                             //情况二：其它情况
            
            result -= map(s[i]);
    }
    
    return result;
    
    
}