LeetCode 12. Integer to Roman ( C )-Medium

題目為給定一個阿拉伯數字，將之轉換成羅馬數字的表示方式。

下一題則反過來，把羅馬數字轉換成阿拉伯數字，此為下一題的連結 : LeetCode 13. Roman to Integer

原文題目如下

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, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 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.

 

Example 1:

Input: num = 3
Output: "III"
Example 2:

Input: num = 4
Output: "IV"
Example 3:

Input: num = 9
Output: "IX"
Example 4:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
 

Constraints:

1 <= num <= 3999

題目限制數字範圍在 1~3999 之間，故我們的解題策略為透過一系列的 if else 暴力解。

1、先配置回傳的記憶體，並宣告一個變數 i 用來當回傳值的下標，用以一個個儲存羅馬數字。

2、透過 while 迴圈一個個拆出羅馬數字，我們先判斷有幾個 1000 ，接著因為羅馬數字表示 9 與 4 時都是透過減法，把 1 放置於前，代表減一。故每次都要額外檢查 9 或 4 開頭的數字，以此類推當 num 歸零時回傳字串。

下面是我的程式碼

char * intToRoman(int num){
    char *re = (char*) malloc(sizeof(char)*20);
    int i = 0;
    while(num>0){
        if(num>=1000){
            num-=1000;
            re[i++] = 'M';
        }
        else if(num>=900){
            num-=900;
            re[i++] = 'C';
            re[i++] = 'M';
        }
        else if(num>=500){
            num-=500;
            re[i++] = 'D';
        }
        else if(num>=400){
            num-=400;
            re[i++] = 'C';
            re[i++] = 'D';
        }
        else if(num>=100){
            num-=100;
            re[i++] = 'C';
        }
        else if(num>=90){
            num-=90;
            re[i++] = 'X';
            re[i++] = 'C';
        }
        else if(num>=50){
            num-=50;
            re[i++] = 'L';
        }
        else if(num>=40){
            num-=40;
            re[i++] = 'X';
            re[i++] = 'L';
        }
        else if(num>=10){
            num-=10;
            re[i++] = 'X';
        }
        else if(num>=9){
            num-=9;
            re[i++] = 'I';
            re[i++] = 'X';
        }
        else if(num>=5){
            num-=5;
            re[i++] = 'V';
        }
        else if(num>=4){
            num-=4;
            re[i++] = 'I';
            re[i++] = 'V';
        }
        else{
            num--;
            re[i++] = 'I';
        }
        
        
        
    }
    re[i] = '\0';
    return re;
}

下面是時間與空間之消耗

Runtime: 4 ms, faster than 80.79 % of C online submissions for Integer to Roman.

Memory Usage: 5.9 MB, less than 80.46 % of C online submissions for Integer to Roman.

下一題連結 : LeetCode 13. Roman to Integer