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的二维数组，不易出错。

解题代码：

private static String method(int number) {
         // 入参保护
         if (number > 3999 || number < 1) {
             return null;
         }
         // 结果集
         StringBuffer result = new StringBuffer();
         // 罗马字符集
         char[][] romanArray = new char[][] { { 'I', 'V' }, { 'X', 'L' }, { 'C', 'D' }, { 'M' } };
         // 创建副本确定最高位数
         int maxLevel = 0;
         int copyNumber = number;
         while (copyNumber > 0) {
             copyNumber /= 10;
             maxLevel++;
         }
         while (--maxLevel >= 0) {
             // 罗马数字从左往右是最高位的
             int currentNumber = (int) ((number / Math.pow(10, maxLevel)) % 10);
             // 4,9特别处理
             if (currentNumber == 4) {
                 result.append("" + romanArray[maxLevel][0] + romanArray[maxLevel][1]);
             } else if (currentNumber == 9) {
                 result.append("" + romanArray[maxLevel][0] + romanArray[maxLevel + 1][0]);
             } else {
                 // 大于等于5处理
                 if (currentNumber / 5 == 1) {
                     result.append(romanArray[maxLevel][1]);
                 }
                 // 加1
                 for (int i = 0; i < currentNumber % 5; i++) {
                     result.append(romanArray[maxLevel][0]);
                 }
             }
         }
         return result.toString();
     }

测试代码地址：

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：如有不正确或提高效率的方法，欢迎留言，谢谢！