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                 // 加1
31                 for (int i = 0; i < currentNumber % 5; i++) {
32                     result.append(romanArray[maxLevel][0]);
33                 }
34             }
35         }
36         return result.toString();
37     }

測試代碼地址：

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