整数转罗马数字 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

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

罗马数字通过从最高到最低的小数位值转换形成。规则如下：

若该值不是以 4 或 9 开头，选择可从输入中减去的最大符号，附加到结果并减去其值。
若该值以 4 或 9 开头，使用减法形式（如 4=IV，9=IX，40=XL，90=XC，400=CD，900=CM）。
符号 I、X、C、M 最多连续出现 3 次；V、L、D 不能连续出现。

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

示例 1

输入：num = 3749

输出："MMMDCCXLIX"

3000=MMM，700=DCC，40=XL，9=IX。

示例 2

输入：num = 58

输出："LVIII"

50=L，8=VIII。

示例 3

输入：num = 1994

输出："MCMXCIV"

1000=M，900=CM，90=XC，4=IV。

💭 模拟答题者思考

1. 最直接：把 1~3999 每个数都预转成罗马串存哈希表，查询 O(1)——可行但毫无算法味，也学不到转换规则。

2. 按位拆分？个位、十位、百位、千位分别映射——可以，但要手写 4×10 种情况（含 4、9 的减法形式），代码冗长易错。

3. 关键观察：罗马数字是贪心的——每次取不超过当前 num 的最大「合法片段」（1000/900/500/400/.../1），拼上对应符号，减去该值，重复直到 num=0。

4. 为什么贪心正确？合法片段集合固定且有序，每次取最大片段等价于从高位到低位逐段分解，与手工转换一致。

5. 实现技巧：把减法形式（900、400、90、40、9、4）也放进值数组，这样内层只需 while num >= vals[i] 循环，无需特判 4 和 9。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`vals, syms`	int[], string[]	定义：预置的「数值-符号」对，按从大到小排列，含减法形式（900=CM 等）维护：固定不变，覆盖 1~3999 所有合法片段更新：无需更新，遍历时按下标 `i` 依次尝试
`num`	int	定义：待转换的剩余整数值维护：每拼出一个符号就从 `num` 中减去对应数值更新：`num -= vals[i]`，直到 `num == 0`
`res`	string	定义：已拼接的罗马数字结果维护：每次确定一个符号后追加到末尾更新：`res += syms[i]`
`i`	int	定义：当前尝试的「数值-符号」对下标维护：从 0 遍历到末尾；同一 `i` 可重复使用（如 3000 拼三次 M）更新：当 `num < vals[i]` 时 `i++` 尝试更小的值

⌨️ 落码步骤

1. 预置 vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1] 和对应 syms

2. 初始化空字符串 res，i = 0

3. 当 num > 0：若 num >= vals[i]，则 res += syms[i]，num -= vals[i]；否则 i++

4. num == 0 时返回 res

💻 代码实现

class Solution:
    def intToRoman(self, num: int) -> str:
        vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        res = []
        i = 0
        while num > 0:
            # 当前值能拼就拼，同一符号可重复（如 3000 → MMM）
            while num >= vals[i]:
                res.append(syms[i])
                num -= vals[i]
            i += 1
        return "".join(res)

class Solution {
public:
    string intToRoman(int num) {
        vector<int> vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string res;
        for (int i = 0; num > 0; ++i) {
            while (num >= vals[i]) {
                res += syms[i];
                num -= vals[i];
            }
        }
        return res;
    }
};
// 时间 O(1)（最多 15 次外层 + 常数次内层），空间 O(1)

📈 复杂度分析

时间复杂度 O(1)

空间复杂度 O(1)

⚠️ 常见坑

❗ 值数组必须包含减法形式（900、400、90、40、9、4），否则 4 和 9 无法正确表示。

❗ 内层用 while num >= vals[i] 而非 if，否则 3000 只能拼一个 M。

❗ 值数组必须从大到小排列；从小到大会导致先拼 I 再拼 V，结果错误。

🔍 必测边界 Case

Case 1：最小值

num = 1 → "I"

Case 2：减法形式 4 和 9

num = 4 → "IV"，num = 9 → "IX"

Case 3：最大值

num = 3999 → "MMMCMXCIX"（含 900、90、9 三种减法形式）