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"}.

  所以,代码如下:

 1 public String intToRoman(int num) {
 2     String[][] roman = { 
 3             { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
 4             { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
 5             { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }, 
 6             { "", "M", "MM", "MMM" } };
 7     String res = "";
 8     int digit = 0;
 9     while (num != 0) {
10         int remain = num % 10;
11         res = roman[digit][remain] + res;
12         digit++;
13         num /= 10;
14     }
15     return res;
16 }

方案二

  根据上面蓝色标注的部分,我们可以知道,在减数的时候有特定的规律,就是只能减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):

 1 public String intToRoman(int num) {
 2         if(num>=1000) return "M"+intToRoman(num-1000);
 3         if(num>=900) return "CM"+intToRoman(num-900);
 4         if(num>=500) return "D"+intToRoman(num-500);
 5         if(num>=400) return "CD"+intToRoman(num-400);
 6         if(num>=100) return "C"+intToRoman(num-100);
 7         if(num>=90) return "XC"+intToRoman(num-90);
 8         if(num>=50) return "L"+intToRoman(num-50);
 9         if(num>=40) return "XL"+intToRoman(num-40);
10         if(num>=10) return "X"+intToRoman(num-10);
11         if(num>=9) return "IX"+intToRoman(num-9);
12         if(num>=5) return "V"+intToRoman(num-5);
13         if(num>=4) return "IV"+intToRoman(num-4);
14         if(num>=1) return "I"+intToRoman(num-1);
15         return "";
16     }

非递归方式如下:

 1 public String intToRoman(int num) {
 2         String str = "";    
 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         for(int i=0;num!=0;i++){  
 6             while(num >= value[i]){  
 7                 num -= value[i];  
 8                 str += symbol[i];  
 9             }  
10         }  
11         return str;  
12     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

2605
来自专栏数据小魔方

左手用R右手Python系列之——json序列化与反序列化

json格式数据作为如今越来越流行的数据交换格式,几乎已经成为web端数据交互的标准,主流的数据科学语言R,Python都中都有非常完善的半结构化数据与json...

3207
来自专栏小樱的经验随笔

BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法,思维题】

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 4474  So...

2644
来自专栏HansBug's Lab

1677: [Usaco2005 Jan]Sumsets 求和

1677: [Usaco2005 Jan]Sumsets 求和 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 6...

3058
来自专栏数据结构与算法

BZOJ4269: 再见Xor(线性基)

给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。

704
来自专栏数据结构与算法

BZOJ3998: [TJOI2015]弦论(后缀自动机)

第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

1012
来自专栏数据结构与算法

BZOJ3560: DZY Loves Math V(欧拉函数)

$\sum_{i_1 = 0}^{b_1} \sum_{i_2 = 0}^{b_2} \dots \sum_{i_n = 0}^{b_n} \phi( p^{\...

1186
来自专栏HansBug's Lab

2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

3046
来自专栏小樱的经验随笔

BZOJ 3097: Hash Killer I【构造题,思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

2146
来自专栏数据结构与算法

BZOJ2693: jzptab(莫比乌斯反演)

122 HINT T <= 10000 N, M<=10000000

972

扫码关注云+社区

领取腾讯云代金券