LeetCode题目（Python实现）：罗马数字转整数

分手后的思念是犯贱 2023-07-13 05:55 1阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：直接计数
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  想法二：分情况
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  哈希法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

罗马数字包含以下七种字符: `I`， `V`， `X`， `L`，`C`，`D` 和 `M`。  
![在这里插入图片描述][20200310233330354.png]  
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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.

## 想法一：直接计数 ##

### 算法实现 ###

def romanToInt(self, s: str) -> int:
            return s.count('I') + 5 * s.count('V') + 10 * s.count('X') + 50 * s.count('L') + 100 * s.count(
                'C') + 500 * s.count('D') + 1000 * s.count('M') \
                   - 2 * (s.count('IV') + s.count('IX') + 10 * (s.count('XL') + s.count('XC')) + 100 * (
                        s.count('CD') + s.count('CM')))

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 72 ms, 在所有 Python3 提交中击败了24.46%的用户  
**内存消耗** : 13.5 MB, 在所有 Python3 提交中击败了8.90%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(max(m,n))，  
    我们遍历了两个链表所有节点。
 *  空间复杂度：O(max(m,n))  
    需要额外的n或者m个节点来储存和。

## 想法二：分情况 ##

### 算法实现 ###

def romanToInt2(self, s: str) -> int:
    	n = len(s)
    	i = 0
    	Sum = 0
    	while i < n:
    	    temp = s[i]
    	    if temp == 'M':
    	        Sum += 1000
    	    elif temp == 'D':
    	        Sum += 500
    	    elif temp == 'C':
    	        Sum += 100
    	    elif temp == 'L':
    	        Sum += 50
    	    elif temp == 'X':
    	        Sum += 10
    	    elif temp == 'V':
    	        Sum += 5
    	    elif temp == 'I':
    	        Sum += 1
    	    i += 1
    	i = 0
    	while i < n - 1:
    	    temp = s[i:i + 2]
    	    if temp == 'CM' or temp == 'CD':
    	        Sum -= 2 * 100
    	        i += 1
    	    elif temp == 'XC' or temp == 'XL':
    	        Sum -= 2 * 10
    	        i += 1
    	    elif temp == 'IX' or temp == 'IV':
    	        Sum -= 2 * 1
    	        i += 1
    	    i += 1
    	return Sum

### 执行结果 ###

![在这里插入图片描述][2020031100304777.png]

### 复杂度分析 ###

*  时间复杂度：O(n)，
 *  空间复杂度：O(1)

## 哈希法 ##

### 算法实现 ###

def romanToInt2(self, s: str) -> int:
    	Roman2Int = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        Int = 0
    
        for index in range(len(s) - 1):
            if Roman2Int[s[index]] < Roman2Int[s[index + 1]]:
                Int -= Roman2Int[s[index]]
            else:
                Int += Roman2Int[s[index]]
    
        return Int + Roman2Int[s[-1]]

### 执行结果 ###

![在这里插入图片描述][20200311004157817.png]

### 复杂度分析 ###

*  时间复杂度：O(n)，
 *  空间复杂度：O(1)

## 小结 ##

先按照自己的想法设计，一种是直接计数，但是速度很慢，另一种是遍历时分情况加。

看到题解的哈希法才想起来字典，字典这个查找最快的方法我居然没想起来，看来还是修行不够啊=。=

[20200310233330354.png]: https://img-blog.csdnimg.cn/20200310233330354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200310233719266.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[2020031100304777.png]: https://img-blog.csdnimg.cn/2020031100304777.png
[20200311004157817.png]: https://img-blog.csdnimg.cn/20200311004157817.png