第64期-基础数据结构：哈希表 罗马数字转整数

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

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

罗马数字包含以下七种字符: 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:

输入: "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.

初始代码

from typing import List
class Solution:
    def romanToInt(self, s: str) -> int:
        #在此之间填写代码

print(Solution().romanToInt("III"))
print(Solution().romanToInt("IV"))
print(Solution().romanToInt("IX"))
print(Solution().romanToInt("LVIII"))
print(Solution().romanToInt("MCMXCIV"))

2 解题思路

• 标签：哈希表
• 将单个罗马字符或者特殊罗马字符对应的数字存在一个字典中
• 判断字符串中的字符是否是特殊罗马数字，若不是则进行普通罗马数字变化

3 解题方法

from typing import List
class Solution:
    def romanToInt(self, s: str) -> int:
        a={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        b={'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}
        x,i=0,0
        while i<len(s):
            if i+1 < len(s) and s[i:i+2] in b:
                x+=b[s[i:i+2]]
                i+=2
            else:
                x+=a[s[i]]
                i+=1
        return x

print(Solution().romanToInt("III"))
print(Solution().romanToInt("IV"))
print(Solution().romanToInt("IX"))
print(Solution().romanToInt("LVIII"))
print(Solution().romanToInt("MCMXCIV"))

第1-3，16-20行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义字典a用于存放单个罗马字符字符以及其对应的数字
第5行： 定义字典b用于存放特殊情况的罗马字符以及其对应的数字
第6行： 定义变量x，i，分别用于数字存放以及罗马数字字符串索引
第7行： 当索引在罗马字符串长度内时，执行循环
第8行： 判断索引后的两个字符是否存在且是特殊字符
第9行： 若是特殊字符，则加上哈希表b中该字符对应的数字给x
第10行： 由于特殊字符占两个长度，所以索引加二
第11行： 若不是特殊字符，则转到此处
第12行： 由于不是特殊字符，则加上哈希表a中该字符对应的数字给x
第13行： 由于普通字符占1个长度，所以索引加一
第14行： 循环完毕则字符串中所以罗马字符都被遍历到，返回函数结果值x

代码运行结果为：

数据结构讲解

这里用到了基础数据结构：哈希表，简单讲解下这个结构：
哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构
它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表使用方法

1.直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。

2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3. 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码