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 条评论
登录 后参与评论

相关文章

  • Java程序员面试宝典——重要习题整理

    1、下面程序的输出结果是() public class Test { public static void main(String[] arg...

    mukekeheart
  • No.005 Longest Palindromic Substring

    5. Longest Palindromic Substring Total Accepted: 120226 Total Submissions: 50952...

    mukekeheart
  • iOS学习——tableview中带编辑功能的cell键盘弹出遮挡和收起问题解决

      最近在项目中经常用到UITableView中的cell中带有UITextField或UITextView的情况,然后在这种场景下,当我们点击屏幕较下方的ce...

    mukekeheart
  • 2020-09-20:如何判断一个数是质数?

    2.费尔马素性测试法法。费马小定理:假如p是质数,a是整数,且a、p互质,那么a的(p-1)次方除以p的余数恒等于1,即:a^(p-1)≡1(mod p)。

    福大大架构师每日一题
  • 蓝桥杯之全排列函数next_permutation()运用

    在蓝桥杯的题目中大多数都可以运用到全排列函数 充分运用可以节省很多的时间。话不多说来刷题

    用户4492257
  • 用Java实现JVM第七章《方法调用和返回》

    案例介绍 本章节主要用java实现;方法调用指令、返回指令、解析方法符号引用、参数传递等。实现新的指令后我们的虚拟机就可以执行稍微复杂的运算并输出结果。

    小傅哥
  • 用Java实现JVM第七章《方法调用和返回》

    本章节主要用java实现;方法调用指令、返回指令、解析方法符号引用、参数传递等。实现新的指令后我们的虚拟机就可以执行稍微复杂的运算并输出结果。

    小傅哥
  • python中逻辑运算符“+”的特殊之处

    num = num + num 与 num += num 的区别(其他语言中这两种方式可以划等号,但是python中不可以):

    py3study
  • python学习之旅(二)

    py3study
  • 【leetcode刷题】T45-丑数

    Write a program to check whether a given number is an ugly number.

    木又AI帮

扫码关注云+社区

领取腾讯云代金券