本文讲述了python基础编程100例：第64期-基础数据结构：哈希表 罗马数字转整数！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

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

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选的不好，容易产生同义词。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。