LeetCode 12. Integer to Roman 整数转罗马数字

题目

https://leetcode.com/problems/integer-to-roman/

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

讲解

题目是关于怎样把阿拉伯数字转化为罗马数字。

这道题需要有对罗马数字的表示方法的了解。参考wiki百科

一个罗马数字可以由7个基本罗马数字拼凑组成。7个罗马数字分别是 I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。

Symbol I V X L C D M
Value 1 5 10 50 100 500 1,000

通常罗马数字的表示是在在较大的数字的右边记上较小的罗马数字,表示大数字加小数字,如VI (6)。

对于4和9及它们的10的倍数,则不是单纯做加法,需要特殊处理。

Number 4 9 40 90 400 900
Notation IV IX XL XC CD CM

所以通过7个基本罗马数字和6个对于4和9的特殊处理,我们就可以表示用来其他任何罗马数字。

本题解题算法正是演绎用罗马字符拼凑数字。

我们引入两个数组:

  • 一个是存入13个基本的罗马数字符号:M (1000), CM (900), D (500), CD (400), C (100), XC (90), L (50), XL (40), X (10), IX (9), V (5), IV (4) and I (1)。
  • 另一个则是13个对应的阿拉伯数:1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1。

按数值从大到小的顺序试着用罗马字来拼凑数字,拼一次则在字符串加上该罗马字,并把数值从目标数字中减去。

视频教学

Java参考代码

class Solution {
    public String intToRoman(int num) {
        int[] arabics = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < arabics.length; i++) {
            while (num - arabics[i] >= 0) {
                sb.append(romans[i]);
                num = num - arabics[i];
            }            
        }
                
        return sb.toString();
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注