Integer to Roman

Given an integer, convert it to a roman numeral.

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

https://leetcode.com/problems/integer-to-roman/

Discussion

对应关系：

I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;

其中每两个阶段的之间有一个减法的表示，比如900=CM， C写在M前面表示M-C。

范围给到3999，感觉情况不多直接打表其实更快，用代码判断表示估计比较繁琐。

然后就是贪心的做法，每次选择能表示的最大值，把对应的字符串连起来。

Solution

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

string intToRoman(int num) {
        string str;  
        string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  
        int value[]=    {1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1}; 
        for(int i=0;i<sizeof(value)/sizeof(int);++i)
        {
            while(num>=value[i])
            {
                num-=value[i];
                str+=symbol[i];
            }
            if(num == 0) break;
        }
        return str;
    }

Solution: using map (descending order)

这里不能用unordered_map，因为比较是有顺序的，先从1000开始。

class Solution {
public:
    string intToRoman(int num) {
        map<int, string, greater<int>> numeral_map = {{1,    "I"}, {4,   "IV"}, {5,   "V"}, {9,   "IX"},
                                                      {10,   "X"}, {40,  "XL"}, {50,  "L"}, {90,  "XC"},
                                                      {100,  "C"}, {400, "CD"}, {500, "D"}, {900, "CM"},
                                                      {1000, "M"}};
        string result;
        while (num > 0) {
            for (const auto& kvp : numeral_map){
                while (num / kvp.first > 0) {
                    num -= kvp.first;
                    result.append(kvp.second);
                }
            }
        }        
        return result;
    }
};

Solution 3:

这道题主要就在于如何处理每一位digit，并且按照区间不同处理：
1<=digit <=3
digit =4
digit = 5
5<digit<=8
digit =9

string intToRoman(int num) {
        char symbol[7] = { 'I','V','X', 'L','C', 'D','M'};  
       string roman;  
       int scale = 1000;  
       for(int i =6; i>=0; i-=2)  
       {  
         int digit = num/scale;  
          if(digit != 0)  
          {        
            if(digit <= 3)  
            {  
              roman.append(digit, symbol[i]);  
            }  
            else if(digit ==4)  
            {  
              roman.append(1, symbol[i]);  
              roman.append(1, symbol[i+1]);  
            }  
            else if(digit ==5)  
            {  
              roman.append(1, symbol[i+1]);  
            }  
            else if(digit <=8)  
            {  
              roman.append(1, symbol[i+1]);  
              roman.append(digit-5, symbol[i]);  
            }  
            else if(digit ==9)  
            {  
              roman.append(1, symbol[i]);  
              roman.append(1, symbol[i+2]);  
            }  
          }  
          num = num%scale;  
          scale/=10;        
        }  
        return roman;
    }

Solution 最简单解法

string M[] = {"", "M", "MM", "MMM"};
    string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];