12. Integer to Roman

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.

---

本题要求把一个阿拉伯数字转换为罗马数字。 首先要了解罗马数字的表示形式，具体看Roman numerals WIKI。 罗马数字由上左图的7个基本字母组成，直接递归很容易求解。但是会有一些特殊情况，比如4，如果递归求解就是IIII，为了简便，采用5-1也就是IV的形式。上面右图就是基本的特殊情况。考虑特殊情况之后的递归代码如下：

class Solution {
public:
    string work(int num, string cur)
    {
        if (num >= 1000)
            return work(num – 1000, cur + "M");
        if (num >= 500) {
            if (num >= 900)
                return work(num – 900, cur + "CM");
            return work(num – 500, cur + "D");
        }
        if (num >= 100) {
            if (num >= 400)
                return work(num – 400, cur + "CD");
            return work(num – 100, cur + "C");
        }
        if (num >= 50) {
            if (num >= 90)
                return work(num – 90, cur + "XC");
            return work(num – 50, cur + "L");
        }
        if (num >= 10) {
            if (num >= 40)
                return work(num – 40, cur + "XL");
            return work(num – 10, cur + "X");
        }
        if (num >= 5) {
            if (num >= 9)
                return work(num – 9, cur + "IX");
            return work(num – 5, cur + "V");
        }
        if (num < 5) {
            if (num >= 4)
                return work(num – 4, cur + "IV");
            while (num > 0) {
                cur += "I";
                num–;
            }
            return cur;
        }
    }
    string intToRoman(int num) { return work(num, ""); }
};

本代码提交AC，用时32MS，这么多if语句，真是不够优雅。后来看到网上一种解法，简洁漂亮许多，贴出来学习一下：

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

本代码提交AC，用时56MS，比上一版稍慢，不够这版更好看。