LeetCode高频题12：整数转罗马数字
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
文章目录
- LeetCode高频题12：整数转罗马数字
-
- @[TOC](文章目录)
- 题目
- 一、审题
- 打表查表就是了，非常非常容易
- 总结
- @[TOC](文章目录)
题目
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
映射关系为
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。
但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数num，将其转为罗马数字。
1 <= num <= 3999
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、审题
示例 1:
输入: num = 3
输出: “III”
示例 2:
输入: num = 4
输出: “IV”
示例 3:
输入: num = 9
输出: “IX”
示例 4:
输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.
打表查表就是了，非常非常容易
这个题，数字num，转罗马数字字符串
说白了就是从高位看，我num应该是由哪些数字的和，然后将数字对应转化为罗马数字字符串
不过比较特殊的是
1 <= num <= 3999
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
超过1000的都可以让好多M来表示千位，剩余都最多不会超过百
都可以通过下表推导：
0怎么表示？罗马字符没有0，转化的时候就是""
比如20
2个10+0就是XX
204
4位IV，小数大数拼就是大数-小数
200,2个C，0不管，那就叫CCIV
那么随意给你一个num，我们究竟咋拼这个罗马字符串呢？关键就是看你是怎么拆分他们的
像上面204，首先看百位，200，遇到2，就是2个C，CC，
所以咱们能不能直接就把100,200,300,400–900，全部用表格存下来？
遇到百位上是x，那就去查对应表格中的那个罗马字符串
由于数字num范围一定是1 <= num <= 3999
故我们最多只会碰到千位，千位是123
还会碰到百位，百位是1234567890
还会碰到十位，十位是1234567890
还会碰到个位，个位是1234567890
那就达标，在遍历num的高位到低位下标时3 2 1 0
表格就设计为一个二维数组
0维是个位：个位里面又是一个数组，包含0–9的罗马字符串
1维是十位：十位里面又是一个数组，包含10,20–90的罗马字符串
2维是百位：十位里面又是一个数组，包含100,200–900的罗马字符串
3维是千位：千位里面又是一个数组，包含1000,2000–3000的罗马字符串
不会超过3000的
像这样：
代码中这么表示：
String[][] arr = {
{"","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","","","","","",""}
};
我们就按照规则把4，9,40，90,400，900搞出来，0就是空字符串
也就是说，不管是你个位十位百位千位出现0，你索引到的arr[i][0]=“”，拼到结果上就相当于没干
其余的都是正常大数拼小数组合出来的罗马数字字符串
上面这个表，自己在准备罗马数字字符串时别整错了哦
然后，咱们有了表，岂不就非常方便知道我在个十百千位上的数字，应该如何对应了吗？
比如：
num=204
高位–低位3 2 1 0下标
获取每一个位的数字a，其实就是num除1000,100，10 ，1再去模10，就能分别得到千，百，十，个位上的数
3位：204/1000%10=0，去索引arr[3][0]=“”，加到ans=“”
2位：204/100%10=2，去索引arr[2][2]=CC，加到ans=CC
1位：204/10%10=0，去索引arr[1][0]=“”，加到ans=CC
0位：204/1%10=4，去索引arr[0][4]=IV，加到ans=CCIV
ans就是咱们要的数字转罗马数字字符串
总之，通过num除1000,100，10 ，1再去模10，就能分别得到千，百，十，个位上的数a
从高到低位，arr[i][a]就是咱们要的对应罗马数字字符串
这得益于这个num范围不会超过1-3999这么小的范围
就是再大没意义，思路就是达标找罗马字符串映射，拼到ans上，0不管
除了49等数字特殊，其余一律都是凑罗马数字字符串
上面的思想明白了，下面就简单了
手撕代码：
class Solution {
public String intToRoman(int num) {
//映射关系为
//字符 数值
//I 1
//V 5
//X 10
//L 50
//C 100
//D 500
//M 1000
String[][] arr = {
{"","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","","","","","",""}
};
String ans = "";
//总之，通过num除1000,100，10 ，1再去模10，就能分别得到千，百，十，个位上的数a
//从高到低位，arr[i][a]就是咱们要的对应罗马数字字符串
ans += arr[3][num / 1000 % 10];//后面是千位数字a
ans += arr[2][num / 100 % 10];//后面是百位数字a
ans += arr[1][num / 10 % 10];//后面是十位数字a
ans += arr[0][num / 1 % 10];//后面是个位数字a
return ans;
}
}
测试
私下测试一波：
public static void test(){
int num = 204;
System.out.println(intToRomeStr(num));
System.out.println(intToRomeStr(900));
System.out.println(intToRomeStr(3999));
}
public static void main(String[] args) {
test();
}
问题不大
CCIV
CM
MMMCMXCIX
900是M-C
90是C-X
9是X-I
所以呢
3999
3：MMM
900：CM
90：XC
9：IX
拼一波：MMMCMXCIX
总结
提示：重要经验：
1）打表整一个二维数组，0 1 2 3各个维度分别代表0–9，10–900,100–900,1000–3000，每一个数组除了特殊的49啥的是小数拼大数，其余都是大数拼小数，按照命名规则玩就行
2）总之，通过num除1000,100，10 ，1再去模10，就能分别得到千，百，十，个位上的数a，从高到低位，arr[i][a]就是咱们要的对应罗马数字字符串
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。