题目

题解

1. 分类法

每个数量级可以分为4类，1~3，4，5~8，9。因此就使用每个数量级取商然后选择合适的类别进行表达，余数进行下一个数量级商的运算

  • 时间复杂度$O(1)$
  • 空间复杂度$O(1)$
class Solution {
public:
    string intToRoman(int num) {//两种方法。1.分类法
        string res = "";
        char roman[] = {'M','D','C','L','X','V','I'};
        int value[] = {1000,500,100,50,10,5,1};//定义两个数组，写入对应的值
        for(int n=0;n<7;n+=2){//对num用M，C，X，I进行除法运算
            int x = num/value[n];
            if(x<4){ 
                for(int i=0; i<x; i++) res += roman[n];//注意循环的上下限
            }
            else if(x==4){
                res = res + roman[n] + roman[n-1];//注意先后顺序，且不能用+=
            }
            else if(x<9){
                res += roman[n-1];//注意要先加5或50或500的代表数字
                for(int i=5; i<x; i++) res += roman[n];//注意循环的上下限
            } 
            else if(x==9){
                res = res + roman[n] + roman[n-2];//注意先后顺序，且不能用+=
            }//然后分情况进行罗马数字的写入
            num = num%value[n];//余数继续迭代
        }
        return res;
    }
};

2. 贪婪法

  • 时间复杂度$O(1)$
  • 空间复杂度$O(1)$
class Solution {
public:
    string intToRoman(int num) {//两种方法。2. 贪婪算法
        string res = "";//定义结果字符串
        int value[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        string roman[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};//罗列所有的情况，包括主要的数字1，4，5，9
        for(int i=0; i<13;i++){
            while(num >= value[i]){
                num -= value[i];
                res += roman[i];
            }//贪婪算法挨个和所有情况比较
        }
        return res;
    }
};