LeetCode 12. 整数转罗马数字

约 6 分钟
文章信息 11 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 面试经典 150 题 腾讯 字节 华为 微软 美团
标签
字符串 哈希表 数学

题目描述

✅ 12. 整数转罗马数字

image-20260928201202223

image-20260928201202225

image-20260928201202227

题意分析

将 1..3999 内的整数转换为标准罗马数字字符串。基础符号 I、V、X、L、C、D、M 分别表示 1、5、10、50、100、500、1000，整体按十进制位从高到低书写。

每位为 4 或 9 时采用减法写法，合法组合只有 IV、IX、XL、XC、CD、CM。不能任意把较小符号放在较大符号前，也不能只要数值相等就视为标准答案。

解法：按面值从大到小贪心

核心思路

[!blue]

把六个减法组合分别当作面值 4、9、40、90、400、900，与基础符号一起按面值降序排列。随后反复选择不超过剩余数值的最大面值，追加对应符号并扣减，即可统一普通写法与减法写法。

这套贪心来自罗马数字的十进制位规则：处理百、十、个位时，位值为 9 就先取对应的减法组合；位值为 5..8 就先取五倍面值，再补一倍面值；位值为 4 取另一种减法组合；位值为 1..3 则重复一倍面值。千位在本题范围内只需要重复 M。

面值降序让上述分支自动按正确顺序发生。一个十进制位处理完后，剩余值一定低于该位的一倍面值，于是继续处理下一位，不会出现非标准的跨位减法组合。

values[i] 与 symbols[i] 必须一一对应。每次追加后都从 num 扣除相同数值，使已输出部分加上余数始终等于原整数；同一符号有时要连续使用，所以内层是循环。最小面值为一，保证余数最终归零。

解题步骤

  1. 准备降序面值数组及一一对应的符号数组，包含全部基础符号和六个减法组合。
  2. 从最大面值开始，只要当前余数不小于它，就追加对应符号并扣减。
  3. 当前面值不能继续使用时，转向下一个更小面值。
  4. 处理完全部面值后返回拼接结果，余数必然已经归零。

代码实现

class Solution {
    public String intToRoman(int num) {
        int[] values = {
            1000,
            900,
            500,
            400,
            100,
            90,
            50,
            40,
            10,
            9,
            5,
            4,
            1
        };
        String[] symbols = {
            "M",
            "CM",
            "D",
            "CD",
            "C",
            "XC",
            "L",
            "XL",
            "X",
            "IX",
            "V",
            "IV",
            "I"
        };
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            // 减法组合已经放在表中，贪心扣减即可得到合法表示。
            while (num >= values[i]) {
                builder.append(symbols[i]);
                num -= values[i];
            }
        }

        return builder.toString();
    }
}

import "strings"

func intToRoman(num int) string {
    values := []int{
        1000,
        900,
        500,
        400,
        100,
        90,
        50,
        40,
        10,
        9,
        5,
        4,
        1,
    }
    symbols := []string{
        "M",
        "CM",
        "D",
        "CD",
        "C",
        "XC",
        "L",
        "XL",
        "X",
        "IX",
        "V",
        "IV",
        "I",
    }
    builder := strings.Builder{}

    for i := 0; i < len(values); i++ {
        // 面值表覆盖普通写法和减法写法。
        for num >= values[i] {
            builder.WriteString(symbols[i])
            num -= values[i]
        }
    }
    return builder.String()
}

复杂度分析

  • 时间复杂度：$O(1)$。面值表固定为 13 项，且在 1 <= num <= 3999 内输出长度至多 15。
  • 空间复杂度：$O(1)$。两张表大小固定；除返回字符串外只使用常数个变量。

关键点总结

[!green]

  • 六个减法组合必须作为独立面值参与贪心，不能事后修补。
  • 降序是正确性前提，它让每个十进制位独立生成标准写法。
  • 同一符号可能重复，内层用 while；追加符号和扣减数值必须同步。

易错点总结

[!yellow]

  • 漏掉减法面值，会用重复普通符号替代必须使用的减法组合，产生非标准表示。
  • 面值与符号数组必须同序对齐，否则扣减的数值和输出文本不一致。
  • 内层应使用 while，只执行一次的 if 会漏掉同一面值需要重复使用的情况。
  • 每次追加后必须扣减 num，否则循环条件不会改变。
  • 不能自行增加任意两符号的减法组合，标准写法只允许题目规定的六种。

相似题目

题目 难度 关联与区别
13. 罗马数字转整数 简单 互为编码与解析方向；本题优先输出特殊减法组合，原题识别小值在大值前的含义。
273. 整数转换英文表示 困难 同样把数值分解成规范文本片段，原题按千进位分组，本题按罗马数值符号贪心分解。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/70984495
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！