[Leetcode] Interger to roman 整数转成罗马数字

Given an integer, convert it to a roman numeral.

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

题意：将整数转换成罗马数字，这里就需要对什么是罗马数字有一些了解。一下部分摘选于百度百科。

计数方法：

1）相同的数字连写，所表示的数等于这些数字相加得到的数，如：III=3；

2）小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：VIII=8、XII=12；

3）小的数字（限于I、X、和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：IV=4、IX=9；

4）正常使用时，连写的数字重复不得超过三次；

5）在一个数的上面画一条横线，表示这个数扩大1000倍。

组数规则：

1）基本数字I、X、C中的任何一个、自身连用构成数目、或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能一个；

2）不能把基本数字V、L、D中的任何一个座位小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目只能用一个；

3）V和X的左边的小数子只能用I；

4）L和C的左边小数字只能用X；

5）D和M左边的小数字只能用C；

规则3~5可以理解为，放在左边的小数字只能是同一级别，额，好吧，具体含义得自己体会。

方法一：题中给出了整数的范围， 用罗马数字给出各个数字对应的表现形式，用二维向量表示。值得注意的是 “” 的位置，求罗马数字的过程可以表示为从个位、十位、百位、千位一步步的计算，在返回值res的求值中，+两段的顺序不能颠倒。代码如下：

 class Solution {

 public:

     string intToRoman(int num)

     {

         vector<vector<string>> strR=

         {

             {"", "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 row=;

         while(num !=)

         {

             int col=num%;

             res=strR[row][col]+res;　　//注意顺序

             row++;

             num/=;

         }

         return res;

     }

 };

方法二：参考Grandyang的博客，使用贪婪算法的解法。建立表格，每次通过查找当前最大的数，减去在查找。和上面解法的区别在于，上面是将每个数量级上的整数一次性转成罗马数字，这个是有点像用天平秤东西一样，从大到小的一个个试。代码如下：

 class Solution {

 public:

     string intToRoman(int num)

     {

         string res;

         vector<int> intVal{,,,,,,,,,,,,};

         vector<string> strRoman{"M","CM","D","CD","C","XC","L","XL","X",

         "IX","V","IV","I"};

         for(int i=;i<intVal.size();++i)

         {

             while(num>=intVal[i])

             {

                 num-=intVal[i];

                 res+=strRoman[i];

             }

         }

         return res;

     }

 };

巴特西

[Leetcode] Interger to roman 整数转成罗马数字

最新文章

热门文章