LeetCode50天刷题计划（Day 9—— 整数转罗马数字（20.40-22.10）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

一、题目

整数转罗马数字

罗马数字包含以下七种字符： 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:
输入: num = 3
输出: “III”

示例 2:
输入: num = 4
输出: “IV”

示例 3:
输入: num = 9
输出: “IX”

示例 4:
输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.

示例 5:
输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示

1 <= num <= 3999

二、思路

想过贪心算法，但是不会写 QAQ，现在觉得算法题最重要的就是理解算法的意思。最后写的是：
把每个输入看成四位数，一位一位处理：如果是4/5、9、直接输出，处理下一位；如果是6/7、8、先输出5，然后和1/2、3一起输出n个1
一上去就打表模拟，没啥意思
以下是贪心的思路：
首先，我们用来确定罗马数字的规则是：对于罗马数字从左到右的每一位，选择尽可能大的符号值。
因此，可以使用一个从大到小顺序排列的哈希表：
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’}
遍历这个哈希表的同时，看此值能否加入字符串中（当前剩余值比表中此项大即可加入）
时间复杂度：O(1)。最坏条件下，循环的次数为哈希表的长度。
空间复杂度：O(1)。

三、代码

1.python

class Solution:
    def intToRoman(self, num: int) -> str:
        return_str = ""#返回字符串
        d=[{
    '1':'M'},{
    '1':'C','4':'CD','5':'D','9':'CM'},{
    '1':'X','4':'XL','5':'L','9':'XC'},{
    '1':'I','4':'IV','5':'V','9':'IX'}]
        s="0"*(4-len(str(num)))+str(num) #补成四位
        for i in range(4):#依次遍历每一位 
            temp=int(s[i])#本轮数字
            if(s[i]=='0'):#0跳过
                continue
            #处理459
            if(i>0 and s[i] in ['4','5','9']):#第一轮不必，千位最多是三，若是特殊数字,直接可以加上
                return_str+=d[i][s[i]]
                continue
            #处理6和7，加入一个5
            if(temp>5):
                temp=temp-5
                return_str+=d[i]['5']
            #处理temp（1/2/3和6/7剩下的）
            return_str+=temp*d[i]['1']
        return return_str           

2.python

class Solution:
    def intToRoman(self, num: int) -> str:
        #定义哈希表
        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'}
        #定义返回值
        re_str=''
        for i in hashmap: #遍历字典的键
            if(num>=i):
                count=num//i #要几个当前字母
                re_str += count * hashmap[i] #加入
                num -= count*i #更新num值
        return re_str