13. 罗马数字转整数

题目：

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

　　例如， 罗马数字 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:

输入: "III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

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

示例 5:

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

解法：

　　思路1：

1、针对题目给出的特定情况（常规 + 特殊），形成哈希字典。

2、针对相邻两个字符属于题目给定的6种特殊情况的处理：

　　【可采用while循环累加的方式：利用索引向后截取两个相邻字符串，若存在于字典时，直接输出对应value，同时跳过下一个字符的处理，否则输出当前字符对应value，依次累加】

3、尾数个例特殊情况处理：

　　【末尾字符以题目规定的6种特殊情况结尾时，i+1<len(s)的while循环，刚好能覆盖处理，而常规情况，却遗漏了末尾字符的处理，因此需要增加尾数字符的识别处理机制】

4、复杂度分析：

• 时间复杂度：O(N)。遍历一遍字符串。
• 空间复杂度：O(1)。未使用多余空间。

 1 class Solution:
 2     def romanToInt(self, s):
 3         s_dict = {‘I‘: 1,‘V‘: 5,‘X‘: 10,‘L‘: 50,‘C‘: 100,‘D‘: 500,‘M‘: 1000,‘IV‘:4,‘XL‘:40,‘CD‘:400,‘IX‘:9,‘XC‘:90,‘CM‘:900}
 4 
 5         s_sum = 0
 6         i = 0
 7         while i+1<len(s):                   # 需要设置成i+1，否则会超出索引界限
 8             if s[i:i+2] in s_dict:
 9                 s_sum += s_dict[s[i:i+2]]
10                 i += 2
11             else:
12                 s_sum += s_dict[s[i]]
13                 i += 1
14                                             # 尾数个例特殊情况处理
15         return s_sum if s[-2:] in s_dict and len(s)>1 else s_sum + s_dict[s[-1]]  

View Code

　　思路2：

1、针对题目给出的常规情况，形成哈希字典。

2、找出6种特殊情况规律：相邻两个字符，左字符对应value值 < 右字符对应value值，并且，对应数值 = 右字符对应的value - 左字符对应的value。

　　【比如：CM = 1000 - 100，XC = 100 - 10，……】

3、遍历每个字符：(左——>右)

　　【如果s[i]代表的value值 < s[i+1]代表的value值，就将累加和 - s[i]代表的value值；否则，将 + s[i] 代表的value值】

4、复杂度分析：

• 时间复杂度：O(N)。遍历一遍字符串。
• 空间复杂度：O(1)。未使用多余空间。

 1 class Solution:
 2     def romanToInt(self, s):
 3         Roman2Int = {‘I‘:1,‘V‘:5,‘X‘:10,‘L‘:50,‘C‘:100,‘D‘:500,‘M‘:1000}
 4         Int = 0
 5 
 6         for index in range(len(s) - 1):           # 预防 index + 1 超出索引界限
 7             if Roman2Int[s[index]] < Roman2Int[s[index + 1]]:
 8                 Int -= Roman2Int[s[index]]
 9             else:
10                 Int += Roman2Int[s[index]]
11 
12         return Int + Roman2Int[s[-1]]

View Code

　　思路3：

1、针对题目给出的特定情况（常规 + 特殊），形成哈希字典。

2、（待补）

3、复杂度分析：

• 时间复杂度：O(N)。遍历一遍字符串。
• 空间复杂度：O(1)。未使用多余空间。 

1 class Solution:
2     def romanToInt(self, s):
3         d = {‘I‘:1, ‘IV‘:3, ‘V‘:5, ‘IX‘:8, ‘X‘:10, ‘XL‘:30, ‘L‘:50, ‘XC‘:80, ‘C‘:100, ‘CD‘:300, ‘D‘:500, ‘CM‘:800, ‘M‘:1000}
4 
5         return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

View Code

★★★  如有问题，欢迎指正：raykindle@163.com  ★★★

13. 罗马数字转整数

原文：https://www.cnblogs.com/raykindle/p/12575018.html