Integer to Roman

LeetCode笔记 阅读(51)

编号 : 12      
难度 : <font color="orange">Medium</font>

# 题目 :  
>
>Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
>
>
>| Symbol | Value  |
>| :-:     | :-:     |
>|I       | 1      |
>|V       | 5      |
>|X       | 10     |
>|L       | 50     |
>|C       | 100    |
>|D       | 500    |
>|M       | 1000   |
>
>For example, two is written as `II` in Roman numeral, just two one's added together. Twelve is written as, `XII`, which is simply `X` + `II`. The number twenty seven is written as `XXVII`, which is `XX` + `V` + `II`.
>
>Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:
>
>`I` can be placed before `V` (5) and `X` (10) to make 4 and 9.  
>`X` can be placed before `L` (50) and `C` (100) to make 40 and 90.  
>`C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.  
>Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.  
>
>**Example 1**:  
>>**Input**: 3  
>>**Output**: "III"  
>
>**Example** 2:  
>>**Input**: 4  
>>**Output**: "IV"  
>
>**Example** 3:  
>>**Input**: 9  
>>**Output**: "IX"  
>
>**Example** 4:  
>>**Input**: 58  
>>**Output**: "LVIII"  
>>**Explanation**: L = 50, V = 5, III = 3.  
>
>**Example** 5:  
>>**Input**: 1994  
>>**Output**: "MCMXCIV"  
>>**Explanation**: M = 1000, CM = 900, XC = 90 and IV = 4.  

# 解 :
```Cpp
class Solution {
public:
    string intToRoman(int num) {
        string ret;

        /* 1000 */
        int quotient = num / 1000;  // 商
        int remainder = num % 1000; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "M";
        }
        
        /* 900 */
        if(remainder >= 900)
        {
            ret += "CM";
            remainder -= 900;
        }

        /* 500 */
        quotient = remainder / 500;  // 商
        remainder = remainder % 500; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "D";
        }

        /* 400 */
        if(remainder >= 400)
        {
            ret += "CD";
            remainder -= 400;
        }

        /* 100 */
        quotient = remainder / 100;  // 商
        remainder = remainder % 100; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "C";
        }

        /* 90 */
        if(remainder >= 90)
        {
            ret += "XC";
            remainder -= 90;
        }

        /* 50 */
        quotient = remainder / 50;  // 商
        remainder = remainder % 50; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "L";
        }

        /* 40 */
        if(remainder >= 40)
        {
            ret += "XL";
            remainder -= 40;
        }

        /* 10 */
        quotient = remainder / 10;  // 商
        remainder = remainder % 10; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "X";
        }

        /* 9 */
        if(remainder >= 9)
        {
            ret += "IX";
            remainder -= 9;
        }

        /* 5 */
        quotient = remainder / 5;  // 商
        remainder = remainder % 5; // 余数
        for(; quotient > 0; quotient--)
        {
            ret += "V";
        }

        /* 4 */
        if(remainder >= 4)
        {
            ret += "IV";
            remainder -= 4;
        }

        /* 1 */
        for(; remainder > 0; remainder--)
        {
            ret += "I";
        }

        return ret;
    }
};
```

# 分析 :  
这道题要求将给定的数字转换成罗马数字,因为数字是有限的,所以可以直接硬编码。  

像这种可以硬编码的问题,也可以使用`手工硬填表`的方式进行简化 :  

```Cpp
class Solution {
public:
    string intToRoman(int num) {
        string ret;
        vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

        for(int i = 0; i < values.size(); i ++)
        {
            while(num >= values[i])
            {
                ret += romans[i];
                num -= values[i];
            }
        }

        return ret;
    }
};
```

Markdown使用 帮助