LeetCode 12. 整数转罗马数字
目录
题目描述
题意分析
输入一个 1 到 3999 的整数，输出它的罗马数字写法。基础符号有七个：
I为 1、V为 5、X为 10、L为 50、C为 100、D为 500、M为 1000，通常从大到小排列并把各符号的值累加。特殊之处在于六种减法写法：4 写作
IV、9 写作IX、40 写作XL、90 写作XC、400 写作CD、900 写作CM。也就是说小符号放在大符号左边时表示相减，而这种写法只允许出现在这六种固定搭配里，不能自由组合出IL、VX之类的东西。约束里有两个关键信号。第一，上界只有 3999，意味着千位最多是 3，只需连写至多三个
M，永远不会用到表示 4000 或更高的符号，整张表的规模是有限且固定的。第二，下界是 1，不存在 0 和负数，罗马数字系统里也没有 0 的写法，因此不用考虑空串输出。边界方面真正需要留意的是那六个减法特例本身：4、9、40、90、400、900 这些数字如果按「累加」的直觉去拆，会拼出
IIII这类不合法的写法，必须单独安排。同时要清楚输出是字符串拼接，全程不做数值运算，也不存在溢出问题。
解法：按面值从大到小贪心
核心思路
若只按七个基础符号贪心，4 会被写成非法的
IIII。因此先把六个减法组合IV、IX、XL、XC、CD、CM也视为不可拆分的面值，再将 13 组「面值—符号」按面值从大到小排列。每次取不超过剩余值的最大面值，追加对应符号并扣掉该面值。循环不变量是：已生成符号的总值加上当前剩余值，始终等于原数；已生成部分是标准罗马数字的合法前缀。
正确性可以按十进制位理解。对任意一位，表中的
9、5、4、1倍面值恰好覆盖该位从 0 到 9 的标准写法；降序处理完这一组后，余数会小于下一档单位，各位互不干扰。因此贪心逐位生成的就是唯一的规范表示。
解题步骤
- 准备严格降序且一一对应的
values、symbols，其中必须包含六个减法组合。- 从最大面值开始遍历；只要
num >= values[i]，就追加符号并扣减面值。- 同一面值可能连续使用，所以内层必须是
while，例如 3000 需要三个M。- 面值 1 保证余数最终归零，返回拼接结果。
以
1994为例：依次选择1000(M)、900(CM)、90(XC)、4(IV)，余数按1994 → 994 → 94 → 4 → 0变化，得到MCMXCIV。
代码实现
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)$。两张表大小固定；除返回字符串外只使用常数个变量。
关键点总结
- 六个减法组合必须作为独立面值参与贪心，不能事后修补。
- 降序是正确性前提，它让每个十进制位独立生成标准写法。
- 同一符号可能重复，内层用
while；追加符号和扣减数值必须同步。- 面试时重点说明「为什么加入减法面值后贪心成立」，而不是只背 13 项表。
易错点总结
- 漏掉减法面值：
4会得到IIII而不是IV，900会得到DCCCC而不是CM。- 面值和符号没有同序对齐：例如 900 对成
CD，数值扣对了但字符错误。- 内层误用
if：3000只能追加一个M，无法得到MMM。- 追加后忘记扣减
num：循环条件永远成立，形成死循环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 13. 罗马数字转整数 | 简单 | 反方向解码，靠比较相邻符号大小判断该加还是该减 |
| 168. Excel 表列名称 | 简单 | 26 进制编码但从 1 开始计数，每轮需先减一再取余 |
| 171. Excel 表列序号 | 简单 | 168 的逆过程，按位累乘累加还原十进制数值 |
| 273. 整数转换英文表示 | 困难 | 按三位一组分段递归，还要处理空格拼接与 20 以内的不规则词 |