罗马数字与整数相互转换

悠悠 2022-12-23 12:28 155阅读 0赞

**[罗马数字转整数][Link 1]**

*  **题目描述**

**罗马数字包含以下七种字符****:** `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）给定一个罗马数字，将其转换成整数。输入确保在** **1** **到** **3999** **的范围内。** ###

**示例** **1:**

输入: "III"

输出: 3

**示例** **2:**

输入: "IV"

输出: 4

**示例** **3:**

输入: "IX"

输出: 9

**示例** **4:**

输入: "LVIII"

输出: 58

解释: L = 50, V= 5, III = 3.

**示例** **5:**

输入: "MCMXCIV"

输出: 1994

解释: M = 1000, CM = 900, XC = 90, IV = 4.

*  **问题分析**

**根据示例5****进行分析：**

**MCMXCIV**

**读到第一个字符为****M,****后一个为****C M>C****所以直接相加，初始化****sum=0,sum=sum+s\[0\]=1000**

**当字符读到第二个字符C****，后一个为M C<M****，后面的字符大，sum=sum-s\[1\]=1000-100=900**

**当字符读到第三个字符M****，后一个为X X<M****，后面的字符小，sum=sum+s\[2\]=900+1000=1900**

**当字符读到第四个字符X****，后一个为C C>X****，后面的字符大，sum=sum-s\[3\]=1900-10=1890**

**当字符读到第五个字符C****，后一个为I C>I****，后面的字符小，sum=sum+s\[4\]= 1890+100=1990**

**当字符读到第六个字符I****，后一个为V V>I****，后面的字符大，sum=sum-s\[5\]= 1990-1=1989**

**当字符读到第七个字符V，后一个为null 为空直接相加，sum=sum+s\[6\]= 1989+5=1994**

*  **解题思路**

理解罗马数字的组合时可以看成左右两部分，从左往右扫一遍s，创建hash表存储key和value

如果遇到右边比左边大的，则左边的这一部分便是负的，否则直接加到底就好

*  **具体代码如下：**

class Solution {
    public:
        int romanToInt(string s) {
            //创建hash表
            map<char,int>m={
       {'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
            int tmp,sum=0;
            for(int i=0;s[i]!='\0';i++)
            {
                tmp=m[s[i]];
                if(s[i+1]&&m[s[i+1]]>m[s[i]])
                {
                    sum=sum-tmp;
                }
                else
                    sum=sum+tmp;
            }
            return sum;
        }
    };

### **（2）给定一个整数，将其转换成罗马数字。输入确保在** **1** **到** **3999** **的范围内。** ###

**示例 1:**

输入: 3  
输出: "III"  
**示例 2:**

输入: 4  
输出: "IV"  
**示例 3:**

输入: 9  
输出: "IX"  
**示例 4:**

输入: 58  
输出: "LVIII"  
解释: L = 50, V = 5, III = 3.  
**示例 5:**

输入: 1994  
输出: "MCMXCIV"  
解释: M = 1000, CM = 900, XC = 90, IV = 4.

*  **解题思路：**

**（1）暴力匹配，硬解码 从高位到低位 逐位处理**

**比如：**

**使用模运算和除法运算，可以得到我们数字中每个位上的数字。**  
**thousands\_digit = integer / 1000  
hundreds\_digit = (integer % 1000) / 100  
tens\_digit = (integer % 100) / 10  
ones\_digit = integer % 10  
然后，我们可以简单地在硬编码表（可通过容器或数组创建）中查找这些结果，并将结果附加在一起**

*  **具体代码如下：**

class Solution {
    public:
        string intToRoman(int num) {
            vector<string> thousand = { "", "M", "MM", "MMM" };
            vector<string> hundred = { "", "C", "CC", "CCC", "CD", "D","DC","DCC","DCCC","CM" };
            vector<string> decad = { "", "X", "XX", "XXX", "XL", "L","LX","LXX","LXXX","XC" };
            vector<string> unit = { "", "I", "II", "III", "IV", "V","VI","VII","VIII","IX" };
    
            string out = thousand[num / 1000];
            out += hundred[(num % 1000) / 100];
            out += decad[(num % 1000 % 100) / 10];
            out += unit[num % 1000 % 100 % 10];
            return out;
        }
    };

**（2）贪心算法：**

**例如，假设我们需要将数字设为478。**

**478 中最大的符号是 CD（值 400）。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

**Roman Numeral so far: CD  
Integer remainder: 478 - 400 = 78  
我们在 78 的基础重复以上步骤，最大的符号是 L（值 50）。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

**Roman Numeral so far: CDL  
Integer remainder: 78 - 50 = 28  
在 28 的基础重复以上步骤，最大的符号是 X （值 10）。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

**Roman Numeral so far: CDLX  
Integer remainder: 28 -10 = 18  
在 18 的基础重复以上步骤，最大的符号是 X （值 10）。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

**Roman Numeral so far: CDLXX  
Integer remainder: 18 - 10 = 8  
在 8 的基础重复以上步骤，最大的符号是 V （值 5）。**

**Roman Numeral so far: CDLXXV  
Integer remainder: 8 - 5 = 3**

**在 3 的基础重复以上步骤，最大的符号是 I （值 1）  
最后，用 I 表示 1，完成转换。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

**Roman Numeral so far: CDLXXVIII  
Integer remainder: 1 - 1 = 0**

*  具体代码如下：

class Solution {
    public:
        string intToRoman(int num) {
            string res;
            vector<int> values={1000,900,500,400,100,90,50,40,10,9,5,4,1};
            vector<string> symbol={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
            for(int i=0;i<values.size()&&num>0;i++)
            {
                while(num>=values[i])
                {
                    res.append(symbol[i]);
                    num-=values[i];
                }
            }
            return res;
        }
    };

参考来源：Leetcode算法题

[Link 1]: https://leetcode-cn.com/problems/roman-to-integer/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221120/7f9c49807f2a44e497f70545a3dda48a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221120/3107d07d614e420891b95ba0e7abb694.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221120/9ae683f05c4d40259f6afca7533088f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201126104134261.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201126104154195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx,size_16,color_FFFFFF,t_70