LeetCode-12 整数转罗马数字

  • 题目:12. 整数转罗马数字
  • 难度:中等
  • 分类:数学、字符串
  • 解决方案:整数比较

今天我们学习第12题整数转罗马数字,这是一道中等题。下面我们看看这道题的题目描述。

题目描述

罗马数字包含以下七种字符:IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如,罗马数字2写做II,即为两个并列的112写做XII,即为X + II27 写做XXVII, 即为XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如4不写做 IIII,而是IV。数字1在数字5的左边,所表示的数等于大数5减小数1 得到的数值4。同样地,数字9表示为IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5)X (10) 的左边,来表示 49
  • X 可以放在 L (50)C (100) 的左边,来表示 4090
  • C 可以放在 D (500)M (1000) 的左边,来表示 400900

给定一个整数,将其转为罗马数字。输入确保在 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
  • 小的数字,(限于XC)在大的数字的左边,所表示的数等于大数减小数得到的数,如:Ⅳ= 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();
    }
}

图片说明

Github地址

LeetCode-12 整数转罗马数字

参考链接

12.整数转罗马数字

图片说明

更多文章请添加公众号:算法半岛(扫描上图二维码即可关注)

#leetcode#
全部评论

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务