罗马数字转整数

题目概述

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

字符	数值
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
3


input: "LVIII"
output: 58
解释: L = 50, V= 5, III = 3.

示例2：

1
2


input: "IX"
output: 9

示例3：

1
2
3


input: "MCMXCIV"
output: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/roman-to-integer

解题思路

####罗马数字特征分析

罗马数字是没有数位的概念，所有数字 从大到小 依次排列，顺序为 从左到右。
罗马数字的结果是 所有子数字的总和 。
在罗马数字中，优先判断6种特殊情况的组合：“IV, IX, XL, XC, CD, CM” 。
最后对所有的子数字（如：IV, X, L等）求和。

算法思路

首先统计6种特殊情况的出现次数，即 复合字符 出现次数，可用 str.count(“IV”) 来实现。
然后统计所有 单字符 出现的次数，str.count(“I”)。
第一步结果会再第二步中重复计算一次，故，有效单字符次数 = 单字符次数 - 对应的复合字符出现次数。例如：
1 2 3 4

input: "MCMXCIV" 符合字符"CM"次数 = 1 单字符"M"次数 = 2 有效单字符"M"次数 = 2-1 = 1
然后对所有的复合字符、有效单字符求和。

算法实现1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def romanToInt(self, s: str) -> int:
        IV = s.count("IV")
        IX = s.count("IX")
        XL = s.count("XL")
        XC = s.count("XC")
        CD = s.count("CD")
        CM = s.count("CM")
        I = s.count("I")
        V = s.count("V")
        X = s.count("X")
        L = s.count("L")
        C = s.count("C")
        D = s.count("D")
        M = s.count("M")
        result1 = (M-CM)*1000 + (D-CD)*500 + (C-CM-CD-XC)*100 + (L-XL)*50 + (X-XC-XL-IX)*10 + (V-IV)*5 + (I-IV-IX)*1
        result2 = IV*4 + IX*9 + XL*40 + XC*90 + CD*400 + CM*900
        result = result1 + result2
        return result

执行用时：72 ms, 在所有 Python3 提交中击败了28.88%的用户。
内存消耗：13.6 MB, 在所有 Python3 提交中击败了6.45%的用户。

算法实现2

算法1，单纯是通过枚举来实现：罗马数字转换为整数。可以换一种思路：

首先，计算所有的单字符的和，这里面包含了对 复合字符的拆分，多计算了一部分值。
复合字符特征：如CM，第一个字符C一定比第二个字符M值小。
第一步多计算的值是什么呢？
- 罗马数字包含6种复合字符任意一个或多个，则一定会多计算一部分值。且多计算的值，至于复合字符有关，与有效单字符没有关系。
  1 2 3 4 5
  
  如：MCMX 算法二第一步：M + C + M + X 真正结果：M + CM + X 多计算的值：C+M - CM = C+M -(M-c) = 2C 即，多计算了复合字符串第一个字符所代表值的2倍
- 如果罗马数字里面没有6种复合复合字符，则不会多计算。
  1 2 3
  
  如：MMX 算法二第一步：M + M + X 真正结果：M + M + X

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        #判断是否存在复合字符，并减去多计算的值
        value1 = 0
        for i in range(len(s)-1):
            if d[s[i]]<d[s[i+1]]:
                value1 = value1 - 2*d[s[i]]
        value2 = 0  
        #所有单字符求和
        for i in range(len(s)):
            value2 =value2 + d[s[i]]

        return value2+value1

执行用时：52 ms, 在所有 Python3 提交中击败了93.13%的用户。
内存消耗：13.6 MB, 在所有 Python3 提交中击败了6.45%的用户。

Contents

题目概述

解题思路

算法思路

算法实现1

算法实现2