Problem: 12. 整数转罗马数字

• 思路
• 解题方法
• 复杂度
• Code

思路

暴力破解 + 转换

解题方法

由思路可知

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

char* intToRoman(int num) {
    char *s = (char*)malloc(sizeof(char)*4000), *p = s;
    while(num > 0) {
        if(num >= 1000) {
            num -= 1000;
            *(p++) = 'M';
        } else if(num >= 900) {
            num -= 900;
            *(p++) = 'C';
            *(p++) = 'M';
        } else if(num >= 500) {
            num -= 500;
            *(p++) = 'D';
        } else if(num >= 400) {
            num -= 400;
            *(p++) = 'C';
            *(p++) = 'D';
        } else if(num >= 100) {
            num -= 100;
            *(p++) = 'C';
        } else if(num >= 90) {
            num -= 90;
            *(p++) = 'X';
            *(p++) = 'C';
        } else if(num >= 50) {
            num -= 50;
            *(p++) = 'L';
        } else if(num >= 40) {
            num -= 40;
            *(p++) = 'X';
            *(p++) = 'L';
        } else if(num >= 10) {
            num -= 10;
            *(p++) = 'X';
        } else if(num >= 9) {
            num -= 9;
            *(p++) = 'I';
            *(p++) = 'X';
        } else if(num >= 5) {
            num -= 5;
            *(p++) = 'V';
        } else if(num >= 4) {
            num -= 4;
            *(p++) = 'I';
            *(p++) = 'V';
        } else {
            num -= 1;
            *(p++) = 'I';
        }
    }
    *p = 0;
    return s;
}