LeetCode 12. 整数转罗马数字
题目
- 难度：中等
- 题型分类：数学、字符串、查表法
- 题目链接：整数转罗马数字
给定整数num，将其转换为罗马数字。
罗马数字的基本符号如下：
| 符号 | I | V | X | L | C | D | M |
|---|---|---|---|---|---|---|---|
| 数值 | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
按千位、百位、十位、个位依次转换并拼接。其中以下数值使用减法形式：
4 → IV 9 → IX 40 → XL 90 → XC 400 → CD 900 → CMI、X、C、M最多连续出现三次；V、L、D不重复使用。
示例
输入：num = 3749 输出："MMMDCCXLIX" 解释：3000 + 700 + 40 + 9 → MMM + DCC + XL + IX。 输入：num = 58 输出："LVIII" 解释：50 + 8 → L + VIII。 输入：num = 1994 输出："MCMXCIV" 解释：1000 + 900 + 90 + 4 → M + CM + XC + IV。数据范围
1 <= num <= 3999
解题思路
使用查表法，提前保存每一位对应的罗马数字：
R[0]：个位，表示0～9。R[1]：十位，表示0～90，步长为10。R[2]：百位，表示0～900，步长为100。R[3]：千位，表示0～3000，步长为1000。
分别提取四个数位，从高到低查表拼接：
千位：num / 1000 百位：num / 100 % 10 十位：num / 10 % 10 个位：num % 10以上除法均为整数除法。数位为0时，对应空字符串，不添加任何符号。
- 时间复杂度：
O(1)，题目范围内只需固定次数的查表与拼接。 - 空间复杂度：
O(1)，映射表及结果长度均有固定上限。
Java
classSolution{publicStringintToRoman(intnum){String[][]R={{"","I","II","III","IV","V","VI","VII","VIII","IX"},{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},{"","M","MM","MMM"}};returnR[3][num/1000]+R[2][num/100%10]+R[1][num/10%10]+R[0][num%10];}}C++
classSolution{public:stringintToRoman(intnum){vector<vector<string>>R={{"","I","II","III","IV","V","VI","VII","VIII","IX"},{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},{"","M","MM","MMM"}};returnR[3][num/1000]+R[2][num/100%10]+R[1][num/10%10]+R[0][num%10];}};Python 3
classSolution:defintToRoman(self,num:int)->str:R=[["","I","II","III","IV","V","VI","VII","VIII","IX"],["","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"],["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],["","M","MM","MMM"]]return(R[3][num//1000]+R[2][num//100%10]+R[1][num//10%10]+R[0][num%10])
