2019-05-11 | 算法 | UNLOCK

罗马数字与整数的相互转换

题目描述:

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值
 I             1
 V             5
 X             10
 L             50
 C             100
 D             500
 M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例:

  • 罗马数字转整数
      输入: "LVIII"
      输出: 58
      解释: L = 50, V= 5, III = 3.
    
  • 整数转罗马数字
      输入: 1994
      输出: "MCMXCIV"
      解释: M = 1000, CM = 900, XC = 90, IV = 4.
    

说下规则

四个规则:

  1. 相同的数字连写, 所表示的数等于这些数字相加得到的数。如 XXX表示 30
  2. 小的数字在大的数字的右边, 所表示的数等于这些数字相加得到的数 如VIII 表示8
  3. 小的数字(限于I, X, C)在大的数字的左边, 所表示的数等于大数减去小的数: 如IV 表示4
  4. 在一个数的上面画一条横线, 表示这个数增值1000倍(由于题目只考虑4000以内的数,所以这条规则不用考虑。)

五个组数规则:

  1. I, X, C: 最多只能连用3个, 如果放在大数的左边,只能用1个。
  2. V, L, D: 不能放在大数的左边,只能使用一个。
  3. I 只能用在V和X的左边。 IV表示4, IX表示9
  4. X只能放在L,C左边。 XL 表示40, XC表示90
  5. C只能用在D, M左边。 CD 表示400, CM表示900

解题思路

  • 罗马数字转整数
    此种题目较为复杂,因为不知道大数在左边还是右边,所以存在两种情况,需要判断一下下:

    • 小的数在左边,大的数字在右边(例 : IV,参照上述6种特殊情况)
    • 小的数在右边,大的数字在左边(例 : VI表示6,即所有数字相加之和)
  • 整数转罗马数字

    • 通过组合数字来拆分,使程序能够实现连加的方法.举个栗子:
      给定一个已知数字,假设为10,然后再给定一组数字(即数组[15,8,4,2,1]),组合数字的意思就是 : 使用当前所给值10与所给数组中所有元素进行比较,找出第一个小于或等于所给当前值10的数组元素,即8,然后从所给已知值中减去该值,用余数与数组中的下一个元素继续进行比较,同理找到小于或者等于该余数的值,然后继续循环往复,直到找不到满足该条件(当前余数不小于等于数组元素的时候)时,给定数字即为所有被减掉的数字之和.

      画个图更简单 :



Talk is cheap,show you my code

  • 罗马数字转整数
      class Solution {
      public:
          int romanToInt(string s) {
              int tagVal[256];
              tagVal['I']=1;
              tagVal['V']=5;
              tagVal['X']=10;
              tagVal['L']=50;
              tagVal['C']=100;
              tagVal['D']=500;
              tagVal['M']=1000;
              int val=0;
              for(int i=0;i<s.length();i++){
                  if(i+1>=s.length()||tagVal[s[i+1]]<=tagVal[s[i]]){
                      val += tagVal[s[i]];
                  }else{
                      val -= tagVal[s[i]];
                  }
              }
              return val;
          }
      };
    
  • 整数转罗马数字
      class Solution {
      public:
          string intToRoman(int num) {
              if(num<=0) return "";
              string ret = "";
              static int number[13]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
              static string flags[13]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
              for (int i=0;i<13&&num>0;i++){
                  if (num<number[i]) continue;
                  while(num>=number[i]){
                      num -= number[i];
                      ret += flags[i];
                  }
              }
              return ret;
          }
      };
    
    OK,今天的算法分享到这就结束了,你懂了么🙂
    欢迎大家来我的Leetcode查看更多内容.

评论加载中