你的位置:首页 > Java教程

[Java教程]No.012:Integer to Roman

题目:

 

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

官方难度:

Medium

翻译:

给定一个整数,将其翻译成罗马数字。输入整数范围是1-3999。

补充资料:

罗马数字规则:
1. 罗马数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。罗马数字中没有“0”。
2. 重复次数:一个罗马数字最多重复3次。
3. 右加左减:
在较大的罗马数字的右边记上较小的罗马数字,表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字,表示大数字减小数字。
4. 左减的数字有限制,仅限于I、X、C,且放在大数的左边只能用一个。
(*) V 和 X 左边的小数字只能用I。
(*) L 和 C 左边的小数字只能用X。
(*) D 和 M 左 边的小数字只能用C。

思路:

1. 确定最高位数。根据位数创建罗马数字对应的二维数组。

2. 根据给定输入的每一位上的数字,匹配二维数组的对应位置,逐字累加至StringBuffer的结果字符串。

3. 先将4和9特殊处理。

4. 不是4和9的情况,判断是否大于等于5,若是,将V(假定正在处理个位数)加至结果字符串。

5. 将当前数字除以5的余数的值,累加I的个数。

解题中可能遇到的困难:

1. 确定最高位时,需要创建一个输入值的副本。

2. 不考虑空间消耗的角度,可以采取定义一个10*n的二维数组,而不是2*n的二维数组,不易出错。

解题代码:

 1 private static String method(int number) { 2     // 入参保护 3     if (number > 3999 || number < 1) { 4       return null; 5     } 6     // 结果集 7     StringBuffer result = new StringBuffer(); 8     // 罗马字符集 9     char[][] romanArray = new char[][] { { 'I', 'V' }, { 'X', 'L' }, { 'C', 'D' }, { 'M' } };10     // 创建副本确定最高位数11     int maxLevel = 0;12     int copyNumber = number;13     while (copyNumber > 0) {14       copyNumber /= 10;15       maxLevel++;16     }17     while (--maxLevel >= 0) {18       // 罗马数字从左往右是最高位的19       int currentNumber = (int) ((number / Math.pow(10, maxLevel)) % 10);20       // 4,9特别处理21       if (currentNumber == 4) {22         result.append("" + romanArray[maxLevel][0] + romanArray[maxLevel][1]);23       } else if (currentNumber == 9) {24         result.append("" + romanArray[maxLevel][0] + romanArray[maxLevel + 1][0]);25       } else {26         // 大于等于5处理27         if (currentNumber / 5 == 1) {28           result.append(romanArray[maxLevel][1]);29         }30         // 加131         for (int i = 0; i < currentNumber % 5; i++) {32           result.append(romanArray[maxLevel][0]);33         }34       }35     }36     return result.toString();37   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q012.java

LeetCode题目地址:

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

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!