【LeetCode】12，整数转罗马数字。难度等级：中等。易错点：使用 python 字典构建哈希表时要考虑哈希表是否有序网站首页 技术杂谈

【LeetCode】12，整数转罗马数字。难度等级：中等。易错点：使用 python 字典构建哈希表时要考虑哈希表是否有序

ctrl A_ctrl C_ctrl V 2024-07-18 06:01:02

简介【LeetCode】12，整数转罗马数字。难度等级：中等。易错点：使用 python 字典构建哈希表时要考虑哈希表是否有序

文章目录

一、题目

在这里插入图片描述

二、我的解法：基于有序哈希表的贪心算法

2.1 使用 dict 构建哈希表

贪心法则：我们每次尽量使用最大的数来表示。比如对于 1994 这个数，如果我们每次尽量用最大的数来表示，依次选 1000，900，90，4，会得到正确结果MCMXCIV。

所以，我们将哈希表按照从大到小的顺序排列，然后遍历哈希表，直到表示完整个输入。

其实整数转罗马数字的问题可以看做一个 “十进制数转不定进制数” 的问题

code：

class Solution:
    def intToRoman(self, num: int) -> str:
        s = ""
        hashmap = {1000: 'M',
                   900: 'CM',
                   500: 'D',
                   400: 'CD',
                   100: 'C',
                   90: 'XC',
                   50: 'L',
                   40: 'XL',
                   10: 'X',
                   9: 'IX',
                   5: 'V',
                   4: 'IV',
                   1: 'I',
                   }
        for key in hashmap:
            if num // key > 0:
            	# num//key 必须加括号，否则先计算 hashmap[key]*num 是 str 类型，str//int 会报错
                s += hashmap[key] * (num // key)
                num = num % key
        return s

这里有一个关键的问题是 for 循环必须按照 1000,900,500… 这样从大到小的顺序进行遍历。而 python 中的字典不一定能保证有序，只有从 py3.6 开始，dict 才是默认有序的，所以使用字典构建有序哈希表容易出错。

为了保证哈希表的有序性，可以使用两个 list / tuple 构建有序哈希表。

此外，判断语句 if num // key > 0 也可以改为 if num >= key

2.2 使用两个 list / tuple 构建有序哈希表

使用两个 list / tuple 构建的哈希表可以确保有序：

class Solution:
    def intToRoman(self, num: int) -> str:
        RomanNum = ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')
        IntNum = (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
        length = len(RomanNum)

        s = ''
        for i in range(length):
            if num >= IntNum[i]:
                s += RomanNum[i] * (num // IntNum[i])
                num = num % IntNum[i]
        return s