跳到主要内容

12. 整数转罗马数字

题目描述​

给你一个整数，将其转为罗马数字。

罗马数字的基本符号：

符号值
I1
V5
X10
L50
C100
D500
M1000

特殊减法规则（6种）：

符号值
IV4
IX9
XL40
XC90
CD400
CM900

规则：同一个符号最多连续出现 3 次，超过时使用减法表示。

输入范围：1 ≤ num ≤ 3999

示例：

  • 输入：num = 3，输出："III"
  • 输入：num = 4，输出："IV"
  • 输入：num = 9，输出："IX"
  • 输入：num = 58，输出："LVIII"（L=50，V=5，III=3）
  • 输入：num = 1994，输出："MCMXCIV"（M=1000，CM=900，XC=90，IV=4）

解题思路​

第一步：理解问题本质​

将整数转换为罗马数字的过程，本质上是一个分解问题：把一个数拆成若干罗马数字值的总和，然后拼接对应的符号。

例如 1994 = 1000 + 900 + 90 + 4 = M + CM + XC + IV，结果为 "MCMXCIV"。

关键在于：应该优先使用最大的罗马数字值去分解。这样可以保证用最少的符号表示，且符合罗马数字从大到小排列的规则。

这正是贪心思想：每次贪心地使用当前能用的最大值，直到数字减为 0。

为什么可以贪心？

罗马数字的各个值构成了一个严格降序的序列（1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1），且每个值都能被后面更小的值精确表示或覆盖。从最大值开始贪心，不会导致后续无法表示剩余部分，因为 1 可以表示任意正整数（通过 I 的重复）。

第二步：暴力解法​

用条件判断逐一处理每个位（千位、百位、十位、个位），分别将各位的数字（0-9）映射到对应的罗马符号。

class Solution:
    def intToRoman(self, num: int) -> str:
        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"]

        return (thousands[num // 1000] +
                hundreds[num % 1000 // 100] +
                tens[num % 100 // 10] +
                ones[num % 10])

为什么这个解法不够通用： 它利用了"输入范围限制在 1-3999"这一前提，硬编码了四个位的所有情况。虽然代码简洁，但这种方式不适合推广到更大的数字范围，也不能清晰展示贪心的推导逻辑。

第三步：最优解法——贪心 + 有序映射表​

将所有罗马数字值（包括 6 个减法特例）从大到小排列，对每个值，尽可能多地从 num 中减去该值，同时拼接对应的符号。

class Solution:
    def intToRoman(self, num: int) -> str:
        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"]
        ans = []
        for i in range(len(values)):
            count = num // values[i]   # 当前值能用几次
            ans.append(symbols[i] * count)  # 拼接对应次数的符号
            num -= values[i] * count   # 减去已表示的部分
        return "".join(ans)

为什么这样做是正确的：

  1. 列表 values 严格从大到小排列，保证贪心优先使用最大值。
  2. 对于每个值 v，count = num // v 表示 v 最多能被使用的次数。根据罗马数字规则，每个值最多使用 3 次（减法特例最多使用 1 次），这已经被罗马数字的结构保证，不需要额外限制。
  3. 减去 values[i] * count 后，剩余部分继续由后面更小的值处理。

6 个减法特例为什么要放在对应位置：

以 900 (CM) 为例，它放在 500 (D) 之前。这样当 num >= 900 时，会先用 CM 而不是错误地写成 D + CCCC（但 CCCC 是非法的，C 最多写 3 次）。将减法特例插入正确位置，贪心过程就自然产生了合法的罗马数字。

完整代码实现​

class Solution:
    def intToRoman(self, num: int) -> str:
        # 所有罗马数字值从大到小排列，包含6个减法特例
        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"]
        ans = []
        for i in range(len(values)):
            count = num // values[i]        # 当前值能被用几次
            ans.append(symbols[i] * count)  # 重复拼接对应符号
            num -= values[i] * count        # 减去已表示的部分
        return "".join(ans)

示例推演​

以 num = 1994 为例，期望输出 "MCMXCIV"。

初始：num = 1994，ans = []

i=0：values=1000，count = 1994 // 1000 = 1，ans=["M"]，num = 1994 - 1000 = 994
i=1：values=900， count = 994  // 900  = 1，ans=["M","CM"]，num = 994 - 900 = 94
i=2：values=500， count = 94   // 500  = 0，ans=["M","CM",""]，num = 94
i=3：values=400， count = 94   // 400  = 0，ans=["M","CM","",""]，num = 94
i=4：values=100， count = 94   // 100  = 0，ans=[..., ""]，num = 94
i=5：values=90，  count = 94   // 90   = 1，ans=[...,"XC"]，num = 94 - 90 = 4
i=6：values=50，  count = 4    // 50   = 0，ans=[...,""]，num = 4
i=7：values=40，  count = 4    // 40   = 0，ans=[...,""]，num = 4
i=8：values=10，  count = 4    // 10   = 0，ans=[...,""]，num = 4
i=9：values=9，   count = 4    // 9    = 0，ans=[...,""]，num = 4
i=10：values=5，  count = 4    // 5    = 0，ans=[...,""]，num = 4
i=11：values=4，  count = 4    // 4    = 1，ans=[...,"IV"]，num = 4 - 4 = 0
i=12：values=1，  count = 0    // 1    = 0，ans=[...,""]，num = 0

拼接结果："M" + "CM" + "" + "" + "" + "XC" + "" + "" + "" + "" + "" + "IV" + ""
       = "MCMXCIV"

以 num = 58 为例，期望输出 "LVIII"。

初始：num = 58

i=0~5（1000~90）：count 均为 0，不拼接
i=6：values=50，count = 58 // 50 = 1，ans=["L"]，num = 58 - 50 = 8
i=7~9（40~9）：count 均为 0，不拼接
i=10：values=5，count = 8 // 5 = 1，ans=["L","V"]，num = 8 - 5 = 3
i=11：values=4，count = 3 // 4 = 0，不拼接
i=12：values=1，count = 3 // 1 = 3，ans=["L","V","III"]，num = 0

结果："L" + "V" + "III" = "LVIII"

复杂度分析​

解法时间复杂度空间复杂度说明
硬编码各位O(1)O(1)四个位各查一次表，常数操作
贪心映射表O(1)O(1)映射表长度固定为 13，循环次数固定

由于 num 的范围固定在 1-3999，两种解法的复杂度实际上都是常数级。若 num 可以更大，贪心解法的时间复杂度为 O(num / min_value)，但这里不适用。

易错点总结​

  • 减法特例的顺序：6 个减法特例（IV, IX, XL, XC, CD, CM）必须插入在它们对应位置的前面，否则贪心过程会优先选择较小的值，导致输出错误。例如 900 必须排在 500 之前，否则 900 会被错误地拆分为 D + 大量 C。
  • count 的计算：count = num // values[i] 是整除，表示当前值能用多少次，而非只用一次。例如 num = 3000 时，对 1000 的 count 是 3，拼接 "MMM"。
  • 不需要手动限制次数：合法的罗马数字中每个基本符号最多连续 3 次，减法特例最多 1 次，这是由映射表的结构自动保证的，不需要在代码中额外判断。
  • 空字符串的拼接：symbols[i] * 0 = ""，乘以 0 得到空字符串，"".join() 会自动忽略空字符串，不影响最终结果。

扩展思考​

相关题目：

  • LeetCode 13. 罗马数字转整数：逆向操作，将罗马字符串解析为整数。遇到"小值在大值左边"时，说明是减法特例，需减去而非加上。

贪心的本质：

这道题的贪心策略之所以正确，是因为罗马数字系统具有"局部最优即全局最优"的性质：每次使用当前允许的最大值，不会造成后续无法表示剩余数字（因为 1 是最小单位，可以构成任意正整数）。

相比之下，如果映射表中某些值之间存在间隙（例如缺少 1），贪心就可能失败（经典反例：硬币找零问题中特殊面额会导致贪心不可行）。

代码简洁性： symbols[i] * count 是 Python 中字符串重复的惯用写法，比循环 for _ in range(count): ans.append(symbols[i]) 更简洁，也是面试中展示 Python 熟练度的好机会。

加载评论中...