我的开源
LeetCode: L12. 整数转罗马数字
题目
罗马数字包含以下七种字符：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。
给你一个整数，将其转为罗马数字。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解:
最简单的想法就是数论里面的进制转化. 一般我们在做进制转化的时候. 比如转化为8进制. 会不停的除以8而得到商.具体步骤如下方法一: 最低位开始换算.不需要预估最高有效位
- v = num % 8;
- 把 v 入到结果字串 sb.append(""+v);
- 如果
num / 8 != 0 ; num = num/8;重复执行步骤 1)
- 反转 sb:
sb.reverse()返回:sb.toString();结束方式二: 最高位开始算,但是要预先估计 MSB的位数. 比如4位: 即: 8*8*8*8
v = num / 8*8*8*8;把 v 入到结果字串sb.append(""+v); num = num % 8*8*8*8
v = num / 8*8*8;把 v 入到结果字串sb.append(""+v); num = num % 8*8*8
v = num / 8*8;把 v 入到结果字串sb.append(""+v); num = num % 8*8
v = num / 8;把 v 入到结果字串sb.append(""+v); num = num % 8
v = num ;把 v 入到结果字串sb.append(""+v);
- 返回:
sb.toString();结束
难点
一般的进制是一个稳定的进制.
- 比如8进制的次低位是表示多少个8. 而再高一位表示:
多少个8*8.但是 罗马进制里面的次低位是表示的时不是多少个最低位的值. - 罗马进制是不稳定的. 如下
I 1
II 2
III 3
IV 4
V 5
VI 6
VII 7
VIII 8
IX 9
X 10
XI 11
XII 12
XIII 13
XIV 14
感觉从低位开始取余法.没有一个稳定的进制.
-
1-3
-
4
-
5
-
9
-
10
-
11-13
-
14
-
15
-
19
-
20
但是反过来从高位开始除余.这个是可以稳定分割的.释义: 这个差异的原因是 一般的进制是某一进制的数字是可以在一个稳定位里面简单计算. 比如小于9的可以非常简单的确定为 0-9表示. 但是
罗马进制却要分为很多种情况. (比如位数不确定. 不是简单的 累计). 而反过来计算可行的原因是: 每10进制相交的数位时,可以分割出 多少个100,多少个100,多少个10,多少个1:而每一次都可以得到0-9个进制数.然后在一个进制内(指10进制)可以具体映射成相应的罗马数字
比如: x % 1000 时.剩余的数一定小于1000,即:0-999
在百位上时.0-9 百;
9百时有一个特殊表示.
5百时有一个特殊表示.
4百时有一个特殊表示.
剩余的用x 个C表示.
同时:
十位上的数: 0-9 个十
特殊的: 90:XC
特殊的: 50:L
特殊的: 40:XL( 50左边减一个10)
剩余的用 x 个:X表示
个位上的数: 0-9 个1
特殊的: 9:IX
特殊的: 50:V
特殊的: 40:IV( 5左边减一个1)
剩余的用 x 个:I表示
如上代码实现就是下面的代码:
class Solution {
public String intToRoman(int num) {
StringBuffer sb = new StringBuffer();
int Ms = num / 1000; num = num % 1000;
// 1000
if (Ms >0){
for(int i = 0;i< Ms;i++){
sb.append("M");
}
}
if(num>=900){
sb.append("CM");
num -=900;
// 处理 < 100
}else{
// 处理 500
if(num>=500){
sb.append("D");
num -=500;
int loop = num / 100;
num = num % 100;
for(int i=0;i<loop;i++){ sb.append("C");}
}else{
if(num >= 400){
num = num % 400;
sb.append("CD");
}else{
int loop = num / 100;
num = num % 100;
for(int i=0;i<loop;i++){ sb.append("C");}
}
}
}
if(num>=90){
sb.append("XC");
num -=90;
// 处理 < 10
}else{
// 处理 50
if(num>=50){
sb.append("L");
num -=50;
int loop = num / 10;
num = num % 10;
for(int i=0;i<loop;i++){ sb.append("X");}
}else{
if(num >= 40){
num = num % 40;
sb.append("XL");
}else{
int loop = num / 10;
num = num % 10;
for(int i=0;i<loop;i++){ sb.append("X");}
}
}
}
if(num>=9){
sb.append("IX");
num -=9;
// 处理 < 1
}else{
// 处理 5
if(num>=5){
sb.append("V");
num -=5;
int loop = num / 1;
num = num % 1;
for(int i=0;i<loop;i++){ sb.append("I");}
}else{
if(num >= 4){
num = num % 4;
sb.append("IV");
}else{
int loop = num; /* / 1; */
//num = num % 1;
for(int i=0;i<loop;i++){ sb.append("I");}
}
}
}
return sb.toString();
}
}
运行结果:
执行用时：4 ms, 在所有 Java 提交中击败了99.97%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了39.59%的用户
通过测试用例：
实际上面我们把罗马的进制里面的 10 , 100, 1000与十进制的对应起来了. 其实我们还可以把 10以内的数再细化为 4进制,5,9进制. 这个只是不像10进制的位没有值的时候用0补进制位. ( 没有值的时候不出现任何此值 ) 这个10以 内的进制更像是一个二级进制.
大于10的数一定应该用 X 表示. 比如12: XII , 而不应该用 9+3: IXIII.
基于上,一个10以内的数只会出现 1,4,5,9进制中的其中一种. 也就是没有值的时候,什么都不用写. 这个也是 上面一条 小于10的数. 从下一进制分割是先分的9.
class Solution {
public String intToRoman(int num) {
// num 预处理. 确保不会大于3999
int[] jz = {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"};
//num = num % 4000;
StringBuffer sb = new StringBuffer();
for (int i = 0;i< jz.length;i++){
int cnt = num / jz[i];
num = num % jz[i];
while(cnt-- > 0){
sb.append(symbols[i]);
}
}
return sb.toString();
}
}
执行结果
执行用时：4 ms, 在所有 Java 提交中击败了99.97%的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了65.49%的用户
通过测试用例：
结语
其实两者是一样的.只是第二个算法只是更进一步的把规律总结出来. 直接查表进行计算而已.同时
- 这个低进制位如果不存在值,是不用补零的.这个在 所有的位上都是成立的.
- 反过来说,这个表意的字符本身就是带有有效位的信息在里面. 比如我们一般的十进制是 都用 0-9 .但是这里却不用相同的 I , 而用10用 X , 100用
C.也就是说符号本身是带位数信息的.