12. 整数转罗马数字
题目描述
罗马数字用七个符号表示：I=1，V=5，X=10，L=50，C=100，D=500，M=1000。
输入整数 num，返回它的罗马数字写法。转换按十进制位从高到低逐位进行，每一位单独写出后再拼接。
某一位是 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，拼起来就是答案。注意 49 要拆成 40 和 9，不能写成 IL。
示例 2
输入：num = 58 输出："LVIII"
解释：50 是 L，8 是 VIII。
示例 3
输入：num = 1994 输出："MCMXCIV"
解释：1000 是 M，900 是 CM，90 是 XC，4 是 IV。
数据范围
1 <= num <= 3999
解题思路：贪心：从大到小减去符号值
把 6 个减法形式也当成普通符号，得到 13 个面值，从大到小排列。贪心：每次选不超过 num 的最大面值，减去它并写下对应符号，直到 num 变成 0。这与罗马数字“按千百十个位从高到低写”的规则完全一致。
为什么正确
处理到面值 v 时，已写出的 ans 对应的数值加上剩余的 num 始终等于原始输入，且 num 小于之前所有面值。
复杂度分析
面值表只有 13 项，输出长度最多 15，时间与空间都是 O(1)。
易错点
只用 7 个基本符号做贪心会得到 IIII、VIIII 这样的非法写法；必须把 CM、CD、XC、XL、IX、IV 加进面值表，并且严格按从大到小的顺序。还要用 while 而不是 if，因为 M、C、X、I 可以重复至多 3 次。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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']
ans = []
for v, s in zip(vals, syms):
while num >= v:
num -= v
ans.append(s)
return ''.join(ans)class Solution {
public String intToRoman(int num) {
int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder ans = new StringBuilder();
for (int k = 0; k < 13; k++) {
while (num >= vals[k]) {
num -= vals[k];
ans.append(syms[k]);
}
}
return ans.toString();
}
}class Solution {
public:
string intToRoman(int num) {
int vals[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string syms[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string ans;
for (int k = 0; k < 13; k++) {
while (num >= vals[k]) {
num -= vals[k];
ans += syms[k];
}
}
return ans;
}
};func intToRoman(num int) string {
vals := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
syms := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
ans := ""
for k, v := range vals {
for num >= v {
num -= v
ans += syms[k]
}
}
return ans
}var intToRoman = function(num) {
const vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const syms = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
const ans = [];
for (let k = 0; k < 13; k++) {
while (num >= vals[k]) {
num -= vals[k];
ans.push(syms[k]);
}
}
return ans.join('');
};function intToRoman(num: number): string {
const vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const syms = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
const ans: string[] = [];
for (let k = 0; k < 13; k++) {
while (num >= vals[k]) {
num -= vals[k];
ans.push(syms[k]);
}
}
return ans.join('');
}其他解法
贪心法用少量符号和循环生成结果，表达了规则本身；查表法把每一位的结果提前写好，只做拆位和拼接。
解法 2：按位查表拼接 时间 O(1)，空间 O(1)
罗马数字的千、百、十、个位各自独立表示。预先列出每一位 0~9（千位 0~3）对应的罗马字符串，把 num 拆成四个十进制数位后分别查表拼接。
没有循环，操作数固定，也很直观地体现了「各位独立」的规律。代价是要手写 33 个字符串，且只适用于已知上限 3999。
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 // 100 % 10] + tens[num // 10 % 10] + ones[num % 10]class Solution {
private static final String[] THOUSANDS = {"", "M", "MM", "MMM"};
private static final String[] HUNDREDS = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
private static final String[] TENS = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
private static final String[] ONES = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
public String intToRoman(int num) {
return THOUSANDS[num / 1000] + HUNDREDS[num / 100 % 10] + TENS[num / 10 % 10] + ONES[num % 10];
}
}class Solution {
public:
string intToRoman(int num) {
static const string thousands[] = {"", "M", "MM", "MMM"};
static const string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
static const string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
static const string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10];
}
};func intToRoman(num int) string {
thousands := []string{"", "M", "MM", "MMM"}
hundreds := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
tens := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
ones := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
return thousands[num/1000] + hundreds[num/100%10] + tens[num/10%10] + ones[num%10]
}var intToRoman = function(num) {
const thousands = ['', 'M', 'MM', 'MMM'];
const hundreds = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'];
const tens = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'];
const ones = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'];
return thousands[Math.floor(num / 1000)] + hundreds[Math.floor(num / 100) % 10] + tens[Math.floor(num / 10) % 10] + ones[num % 10];
};function intToRoman(num: number): string {
const thousands = ['', 'M', 'MM', 'MMM'];
const hundreds = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'];
const tens = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'];
const ones = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'];
return thousands[Math.floor(num / 1000)] + hundreds[Math.floor(num / 100) % 10] + tens[Math.floor(num / 10) % 10] + ones[num % 10];
};