「这是我参与11月更文挑战的第10天,活动详情查看:2021最后一次更文挑战」
题目分析
罗马数字包含以下七种字符:
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。
- 示例 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.
复制代码
- 提示
1 <= num <= 3999
题目分析
根据题目我们知道,罗马数字由七种类型,外加如4/9/40/90/400/900这几种类型,所以共计有13种类型。
阿拉伯数字 | 罗马数字 |
---|---|
1000 | M |
900 | CM |
500 | D |
400 | CD |
100 | C |
90 | XC |
50 | L |
40 | XL |
10 | X |
9 | IX |
5 | V |
4 | IV |
1 | I |
根据题目我们可以知道,罗马数字会使用尽量大的数字去相加,比如1400,转换成罗马数字是MCD,而不是MCCCC ,所以我们在考虑的时候,就需要用到贪心法则,也就是尽量使用最大的数字表示。
具体有两种写法,其实思路都是一样的,第一种更容易理解。
代码示例一
这种写法就是将num循环,按照最大数逐步递减,假设num=1011:
- 第一次遍历,num>=1000,因此num-1000=11,sb=M;
- 第二次遍历,num>=10,因此num-10=1,sb=MX;
- 第三次遍历,num>=1,因此num-1=0,sb=MXI,结束循环;
class Solution {
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
while(num>0){
if(num>=1000){
sb.append('M');
num-=1000;
}else if(num>=900){
sb.append("CM");
num-=900;
}else if(num>=500){
sb.append('D');
num-=500;
}else if(num>=400){
sb.append("CD");
num-=400;
}else if(num>=100){
sb.append('C');
num-=100;
}else if(num>=90){
sb.append("XC");
num-=90;
}else if(num>=50){
sb.append('L');
num-=50;
}else if(num>=40){
sb.append("XL");
num-=40;
}else if(num>=10){
sb.append('X');
num-=10;
}else if(num>=9){
sb.append("IX");
num-=9;
}else if(num>=5){
sb.append('V');
num-=5;
}else if(num>=4){
sb.append("IV");
num-=4;
}else if(num>=1){
sb.append('I');
num-=1;
}
}
return sb.toString();
}
}
复制代码
执行结果:
执行结果:通过
执行用时:2 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:38 MB, 在所有 Java 提交中击败了43.05%的用户
代码示例二
这种写法其实本质上和第一种没有区别,只是将阿拉伯数字和罗马数字用数组保存,然后遍历values,通过递减num,即可查出num包含不同类型的values个数。
class Solution {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] reps = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public String intToRoman(int num) {
StringBuffer str = new StringBuffer();
for(int i=0;i<values.length;i++){
int value = values[i];
String rep = reps[i];
while(num >= value){
num=num-value;
str.append(rep);
}
if (num == 0) {
break;
}
}
return str.toString();
}
}
复制代码
执行结果:
执行结果:通过
执行用时:3 ms, 在所有 Java 提交中击败了99.83%的用户
内存消耗:37.8 MB, 在所有 Java 提交中击败了72.27%的用户
近期评论