LeetCode--No.012 Integer to Roman

12. Integer to Roman

• Total Accepted: 71315
• Total Submissions: 176625
• Difficulty: Medium

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

思路：

首先，我们得弄清楚罗马数字的计数方式。根据*的介绍：https://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97

　　罗马数字共有7个，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”，与进位制无关。一般认为罗马数字只用来记数，而不作演算。

• 重复数次：一个罗马数字重复几次，就表示这个数的几倍。

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

• 加线乘千：
  • 在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。
  • 同理，如果上方有两条横线，即是原数的1000000（{\displaystyle 1000^{2}}）倍。

• 数码限制：
  • 同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。

方案一　　

　　从根据红色标红的规则，我们知道在个十百千每一位上的数值肯定是只与对应位上的表达形式有关，而不会牵扯到前一位或后一位上。eg:在十位的表达上有X、XX、XXX、XL、L、LX、LXX、LXXX、XC，而个位和百位对应的表达也都有对应的，完全不会影响到十位上对应的表达。所以，只要整数的十位数值为6，则对应表达式一定是千位+LX+各位。

　　所以，就是直接列举出个十百千每一位的表现形式，然后我们计算每一位的数值，用对应的字符串去填充就可以了，特殊的一点事罗马数中没有数值0，所以我们给其对应的为空字符串表示。所以有：

　　【罗马数字】

　　　　个位上的0~9: {"","I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

　　　　十位上的0~9: {"","X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};

　　　　百位上的0~9: {"","C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};

　　　　千位上的0~3: {"","M", "MM", "MMM"}.

　　所以，代码如下：

 public String intToRoman(int num) {
     String[][] roman = {
             { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
             { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
             { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },
             { "", "M", "MM", "MMM" } };
     String res = "";
     int digit = 0;
     while (num != 0) {
         int remain = num % 10;
         res = roman[digit][remain] + res;
         digit++;
         num /= 10;
     }
     return res;
 }

方案二

　　根据上面蓝色标注的部分，我们可以知道，在减数的时候有特定的规律，就是只能减1位且不能跨越一个位数，同时只限于I X C。像上面那个例子，99 不能用IC(100-1)表示，是因为如果一个数字超过90（或等于90），其罗马数字的表示就必须包含一个XC（100-10）。

同理，对I X C都适用这个原则。

　　这个判断，要从最大往下找，如果一个数字是5，那么他就是属于大于等于5，罗马数字包含V，而无需写成IIIII。所以，可以写成递归的方式，代码可以写成如下（代码源自http://www.cnblogs.com/springfor/p/3886459.html）：

 public String intToRoman(int num) {
         if(num>=1000) return "M"+intToRoman(num-1000);
         if(num>=900) return "CM"+intToRoman(num-900);
         if(num>=500) return "D"+intToRoman(num-500);
         if(num>=400) return "CD"+intToRoman(num-400);
         if(num>=100) return "C"+intToRoman(num-100);
         if(num>=90) return "XC"+intToRoman(num-90);
         if(num>=50) return "L"+intToRoman(num-50);
         if(num>=40) return "XL"+intToRoman(num-40);
         if(num>=10) return "X"+intToRoman(num-10);
         if(num>=9) return "IX"+intToRoman(num-9);
         if(num>=5) return "V"+intToRoman(num-5);
         if(num>=4) return "IV"+intToRoman(num-4);
         if(num>=1) return "I"+intToRoman(num-1);
         return "";
     }

非递归方式如下：

 public String intToRoman(int num) {
         String str = "";
         String [] symbol = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
         int [] value = {1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1};
         for(int i=0;num!=0;i++){
             while(num >= value[i]){
                 num -= value[i];
                 str += symbol[i];
             }
         }
         return str;
     }