Integer to Roman

Given an integer, convert it to a roman numeral.

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

罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。

在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
但是，左减时不可跨越一个位数。比如，99不可以用IC（ $100 - 1$ ）表示，而是用XCIX（ $[100 - 10] + [10 - 1]$ ）表示。（等同于阿拉伯数字每位数字分别表示。）
左减数字必须为一位，比如8写成VIII，而非IIX。
右加数字不可连续超过三位，比如14写成XIV，而非XIIII。

所以可能出现的数字只有： 1000(<4) M, 900(<2) CM, 500(<2) D, 400(<2) CD, 100(<4) C, 90(<2) XC, 50(<2) L, 40(<2) XL, 10(<4) X, 9(<2) IX, 5(<2) V, 4(<2) IV, 1(<4) I

只有M, C, X, I 可能出现多次。从左往右执行，则可得到答案。

 1 public class Solution {
 2     public String intToRoman(int num) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         String symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  
 5         int value[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};  
 6         StringBuffer sb = new StringBuffer();
 7         int i = 0;  
 8         while(num != 0){  
 9             if(num >= value[i]){    // minus largest number  
10                 num -= value[i];  
11                 sb.append(symbol[i]);  
12             } else {  
13                 i++;     
14             }  
15         }  
16   
17         return sb.toString();
18     }
19 }

第三遍：

the numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX respectively)
X can be placed before L and C to make 40 (XL) and 90 (XC respectively)
C can be placed before D and M to make 400 (CD) and 900 (CM) according to the same pattern

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

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