Leetcode12: 整数转罗马数字

题目

七个不同的符号代表罗马数字，其值如下：

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

罗马数字是通过添加从最高到最低的小数位值的转换形成的。将小数位转换为罗马数字有以下规则：

如果该值不是 4 或 9 开头，选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头，使用减法形式，表示从以下符号中减去一个符号，例如：
- 4 = 5(V) - 1(I) = IV
- 9 = 10(X) - 1(I) = IX
仅使用以下减法形式：
- 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD), 900 (CM)
只有 10 的幂（I, X, C, M）最多可以连续附加 3 次。
不能多次附加 5(V)、50(L) 或 500(D)。如果需要表示这些值的 4 次或更多，请使用减法形式。

示例 1

输入：num = 3749

输出： “MMMDCCXLIX”

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
40 = XL 由于 50 (L) 减 10 (X)
9 = IX 由于 10 (X) 减 1 (I)

注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

硬编码数字

class Solution:

    THOUSANDS = ["", "M", "MM", "MMM"]
    HUNDREDS = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    TENS = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ONES = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

    def intToRoman(self, num: int) -> str:
        return Solution.THOUSANDS[num // 1000] + \
            Solution.HUNDREDS[num % 1000 // 100] + \
            Solution.TENS[num % 100 // 10] + \
            Solution.ONES[num % 10]

非常暴力的双O(1)方法，看代码直接看懂了。
把如下结构的表示形式直接hardcode上去，再通过模运算和除法算出每一位上的符号组合，最后将结果拼接在一起。

数字	thousands	hundreds	tens	ones
0	-	-	-	-
1	M	C	X	I
2	MM	CC	XX	II
3	MMM	CCC	XXX	III
4	-	CD	XL	IV
5	-	D	L	V
6	-	DC	LX	VI
7	-	DCC	LXX	VII
8	-	DCCC	LXXX	VIII
9	-	CM	XC	IX

洲际酒店往事

值得一提的是，在评论区中看到了和我在考场上类似的解法，只不过我稍微优化了一下，这居然也过了…

class Solution:
    def intToRoman(self, num: int) -> str:
        s = ""
        while num > 0:
            if num >= 1000:
                s += "M"
                num -= 1000
            elif num >= 900:
                s += "CM"
                num -= 900
            elif num >= 500:
                s += "D"
                num -= 500
            elif num >= 400:
                s += "CD"
                num -= 400
            elif num >= 100:
                s += "C"
                num -= 100
            elif num >= 90:
                s += "XC"
                num -= 90
            elif num >= 50:
                s += "L"
                num -= 50
            elif num >= 40:
                s += "XL"
                num -= 40
            elif num >= 10:
                s += "X"
                num -= 10
            elif num >= 9:
                s += "IX"
                num -= 9
            elif num >= 5:
                s += "V"
                num -= 5
            elif num >= 4:
                s += "IV"
                num -= 4
            elif num >= 1:
                s += "I"
                num -= 1
        return s