Integer to Roman

Q: 整数转罗马数字的时间复杂度是多少？

O(1) 。输入最大为 3999，因此贪心循环会检查 13 行表格，并且最多追加 15 个符号。如果允许更大的数字，并用重复的 M 来表示，时间就会随着 num / 1000 增长。

Q: 你能在不遍历数值的情况下，将整数转换为罗马数字吗？

是的。为每个数位建立一张表，存放该数位对应的字符串，例如百位对应 "" 、 C 、 CC 、 CCC 、 CD 、 D 、 DC 、 DCC 、 DCCC 、 CM 。查找 num 的每一位对应的字符串，并将它们拼接起来。它的时间复杂度也是 O(1) ，需要存储 34 个字符串。

Q: 为什么允许的最大数字是 3999？

M 是最大的字母，而且同一个字母不能连续出现四次，因此千位数最多只能写到 MMM ，3999 写作 MMMCMXCIX 。更大的数字会用额外的符号表示，例如在字母上方加一条横线，表示将它乘以 1000。

中等数学与模拟贪心

+10

罗马数字有 7 个字母：M 表示 1000，D 表示 500，C 表示 100，L 表示 50，X 表示 10，V 表示 5，I 表示 1。字母按从大到小的顺序排列并相加，所以 7 写作 VII。同一个字母不会连续出现 4 次：4、9、40、90、400 和 900 分别写作 IV、IX、XL、XC、CD 和 CM，表示较小的字母从其后面的较大字母中减去。只有这 6 种组合会把较小的字母放在前面。

给定一个整数 num，返回它对应的罗马数字。

函数

intToRoman(num: integer) → string

numinteger: 一个介于 1 到 3999 之间的整数
返回值string: num 对应的大写罗马数字

约束条件

1 ≤ num ≤ 3999

示例

输入: num = 49
输出: "XLIX"
解释: 49 是 40 + 9，所以这个数字写作 XL，然后是 IX：XLIX。不允许写成 IL，因为 I 只能在 IV 和 IX 中表示减法。

输入: num = 2026
输出: "MMXXVI"
解释: 2026 没有数字 4 或 9，因此不需要字母组合，只需把字母的值相加：1000 + 1000 + 10 + 10 + 5 + 1 等于 MMXXVI。

输入: num = 944
输出: "CMXLIV"
解释: 944 等于 900 + 40 + 4，每一部分都是一个减法组合：CM、XL 和 IV 连在一起就是 CMXLIV。

进阶

给定一个字符串，你能检查它是否是标准形式的罗马数字吗？接受 XLIX，拒绝 IIII、IL 和 VX？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

将六组减法组合添加到字母表中，作为独立的符号。这样，书写数字就像找零一样：始终选取仍能适用的最大值。输入最大为 3999，因此所需的工作量很小且固定。

先用累加的方式编写，再缩短较长的写法

思路

先忽略这些配对：尽可能多地写 M，然后写 D，依此类推，直到 I。对于 944，会得到 DCCCCXXXXIIII。这种加法形式与标准形式的区别仅在数字为 4 或 9 的位置，而这些位置总是六种较短形式之一：DCCCC 是 CM，CCCC 是 CD，LXXXX 是 XC，XXXX 是 XL，VIIII 是 IX，IIII 是 IV。

先替换 DCCCC，再替换 CCCC，否则 900 会变成 DCD；十位和个位也一样。加法形式最多有 18 个字母（3999），所以工作量是 O(1)，代价是需要再遍历一遍，并使用一些临时字符串。

算法

对于从 M 到 I 的七个字母中的每一个，当 num 大于或等于它的值时，将它追加进去，并在每次追加后减去对应的值。
将 DCCCC 替换为 CM，然后将 CCCC 替换为 CD。
将 LXXXX 替换为 XC，然后将 XXXX 替换为 XL。
将 VIIII 替换为 IX，然后将 IIII 替换为 IV。
返回字符串。

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

对这 13 个值采用贪心策略

思路

按值排列这七个字母和六对字母：M 表示 1000，CM 表示 900，D 表示 500，CD 表示 400，C 表示 100，XC 表示 90，L 表示 50，XL 表示 40，X 表示 10，IX 表示 9，V 表示 5，IV 表示 4，I 表示 1。选择能用上的最大值总是正确的。较低十进制位的所有值都小于上一位的最小值，因此循环会在接触下一位之前结束。在每一位内，表示 9、5、4 和 1 的值能按标准方式写出每个数字：9 用 9 的符号表示，5 到 8 用 5 的符号加上最多三个 1 的符号表示，4 用 4 的符号表示，1 到 3 用 1 的符号表示。

对于 3746，循环会写出 MMM、D、CC、XL、V、I：MMMDCCXLVI。表中有 13 行，答案最多有 15 个字母，因此工作量为 O(1)，只需遍历一遍。

算法

列出从 1000 到 1 的 13 个值及其符号，包括成对的值。
从一个空字符串开始。
对于每一行，当 num 大于或等于该值时，追加符号并减去该值。
完成所有行后，返回该字符串。

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

易错点和边界情况

在表格中把 D 放在 CM 前面。这样 900 就会变成 DCD。
每一行都用 if 代替 while。3000 需要 3 个 M；如果用 if，结果会是 MCMDCDCXCX。
自己编造其他组合。99 是 XCIX，不是 IC；45 是 XLV，不是 VL。
在 C 中，缓冲区太小。最长的答案是 3888，对应 15 个字母，加上结尾的零需要 16 字节；加法形式需要 19 字节。

常见问题3

整数转罗马数字的时间复杂度是多少？

O(1)。输入最大为 3999，因此贪心循环会检查 13 行表格，并且最多追加 15 个符号。如果允许更大的数字，并用重复的 M 来表示，时间就会随着 num / 1000 增长。

你能在不遍历数值的情况下，将整数转换为罗马数字吗？

是的。为每个数位建立一张表，存放该数位对应的字符串，例如百位对应 ""、C、CC、CCC、CD、D、DC、DCC、DCCC、CM。查找 num 的每一位对应的字符串，并将它们拼接起来。它的时间复杂度也是 O(1)，需要存储 34 个字符串。

为什么允许的最大数字是 3999？

M 是最大的字母，而且同一个字母不能连续出现四次，因此千位数最多只能写到 MMM，3999 写作 MMMCMXCIX。更大的数字会用额外的符号表示，例如在字母上方加一条横线，表示将它乘以 1000。

def intToRoman(num):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

num = 49

预期输出

"XLIX"