12. Integer to Roman 整数转罗马数字

Given an integer, convert it to a roman numeral.

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

Difficulty: Medium

罗马字符:	I	V	X	L	C	D	M
阿拉伯数字:	1	5	10	50	100	500	1000

1~9 : I, II, III, IV, V, VI, VII, VIII, IX
10~90 : X, XX, XXX, XL, L, LX, LXX, LXXX, XC
100~900: C, CC, CCC, CD, D, DC, DCC, DCCC, CM
1000~3000: M, MM, MMM

例如: 整数1437的罗马数字为MCDXXXVII.不难发现,千位,百位,十位和个位上的数分别用罗马数字表示了.1000-M,400-CD,30-XXX,7-VII

解法1:

我们可以分为四类,100-300一类,400一类,500-800一类,900最后一类.每一位上的情况都是类似的

class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        char roman[] = {'M','D','C','L','X','V','I'};
        int value[]  = {1000,500,100,50, 10, 5,  1};
        //n+=2 避开除500,除50,除5
        for (int n=0;n < 7;n += 2)
        {
            int x = num / value[n];
            if (x < 4)
                for (int i=1;i<=x;i++) res += roman[n];
            else if (x == 4)
                res = res + roman[n] + roman[n-1];
            else if (x > 4 && x < 9){
                res +=  roman[n-1];
                for (int i=6;i<=x;i++) res += roman[n];
            }
            else if(x==9) res = res + roman[n] + roman[n-2];
            num %= value[n];
        }
        return res;
    }
};

解法2:

本题由于限制了输入数字范围这一特殊性,故而还有一种利用贪婪算法的解法,建立一个数表,每次通过查表找出当前最大的数,减去再继续查表.

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