↖点击上面『算法半岛』
关注『算法半岛』第一时间接收最新文章
> 题目:12. 整数转罗马数字
> 难度:中等
> 分类:数学、字符串
> 解决方案:整数比较
今天我们学习第12题整数转罗马数字,这是一道中等题。下面我们看看这道题的题目描述。
罗马数字包含以下七种字符: I
, V
, X
, L
, C
, D
和 M
。
字符 数值I 1V 5X 10L 50C 100D 500M 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 到 3999 的范围内。
示例 1:
输入: 3输出: "III"
示例 2:
输入: 4输出: "IV"
示例 3:
输入: 9输出: "IX"
示例 4:
输入: 58输出: "LVIII"解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994输出: "MCMXCIV"解释: M = 1000, CM = 900, XC = 90, IV = 4.
题目要求我们将一个整数转为罗马数,并给出了罗马数与整数的对应规则,如下图所示。
根据题目可以归纳出罗马数的基本组成规则:
II=2
XII=12
Ⅰ
、 X
和 C
)在大的数字的左边,所表示的数等于大数减小数得到的数,如: Ⅳ=4
根据罗马数与整数的对应规则和题目中给出的六种特殊情况,我们将这些数从大到小排序,如下图所示:
我们将这些数分为一个一个区间,当我们输入一个整数时,如输入58,我们判断该整数在哪一个区间中,如下图所示:
58∈[50,90)
,因此最高位的罗马数取50所对应罗马数 L
。计算剩下的数,即58-50=8,继续判断该数属于哪一个区间,如下图所示:
8∈[5,9)
,因此该位的罗马数取5所对应罗马数 V
。计算剩下的数,即8-5=3,继续判断该数属于哪一个区间,如下图所示:
3∈[1,4)
,因此该位的罗马数取1所对应罗马数 I
。计算剩下的数,即3-1=2,继续判断该数属于哪一个区间,如下图所示:
2∈[1,4)
,因此该位的罗马数取1所对应罗马数 I
。计算剩下的数,即2-1=1,继续判断该数属于哪一个区间,如下图所示:
1∈[1,4)
,因此该位的罗马数取1所对应罗马数 I
。
综上分析,58所对应的罗马数为 LVIII
。
有了上面的分析过程,我们对整数转为罗马数的转换方式了如指掌,接下来就是用代码实现上面的分析过程。
java
代码如下所示:
class Solution { public String intToRoman(int num) { // 这里使用StringBuilder保存转换后的罗马数, 注意:这里有一个java面试的考点:Java中String、StringBuilder以及StringBuffer的比较 StringBuilder res = new StringBuilder(); // 用数组保存整数区间及其对应的罗马数区间 int[] n = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String[] str = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for(int i=0; i<n.length; i++){ // 判断该整数属于哪一个区间 while(num >= n[i]){ // 找到区间数后,计算剩余数 num -= n[i]; // 添加区间数对应的罗马数 res.append(str[i]); } }
return res.toString(); }}
LeetCode-12 整数转罗马数字:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A12_IntegertoRoman.java
12.整数转罗马数字:https://leetcode-cn.com/problems/integer-to-roman/
更多文章,请关注『算法半岛』
喜欢就点一下在看呀↓