Leetcode:integer_to_roman

Leetcode:integer_to_roman

一、 題目

將給定的數字(阿拉伯數字)轉化成羅馬數字。數字不會大於3999

二、 分析

首先我們要知道神馬是羅馬數字，雖然聽說過，但其實我還真沒有記住，於是就google了下，詳細見下:

個位數舉例

I, 1 】II, 2】 III, 3】 IV, 4 】V, 5 】VI, 6】 VII, 7】 VIII,8 】IX, 9

十位數舉例

X, 10】 XI, 11 】XII, 12】 XIII, 13】 XIV, 14】 XV, 15 】XVI, 16 】XVII, 17 】XVIII, 18】 XIX, 19】 XX, 20】 XXI, 21 】XXII, 22 】XXIX, 29】 XXX, 30】 XXXIV, 34】 XXXV, 35 】XXXIX, 39】 XL, 40】 L, 50 】LI, 51】 LV, 55】 LX, 60】 LXV, 65】 LXXX, 80】 XC, 90 】XCIII, 93】 XCV, 95 】XCVIII, 98】 XCIX, 99 】

百位數舉例

C, 100】 CC, 200 】CCC, 300 】CD, 400】 D, 500 】DC,600 】DCC, 700】 DCCC, 800 】CM, 900】 CMXCIX,999】

千位數舉例

M, 1000】 MC, 1100 】MCD, 1400 】MD, 1500 】MDC, 1600 】MDCLXVI, 1666】MDCCCLXXXVIII, 1888 】MDCCCXCIX, 1899 】MCM, 1900 】MCMLXXVI,1976】 MCMLXXXIV, 1984】 MCMXC, 1990 】MM, 2000 】MMMCMXCIX, 3999】

正好有我們要求的最大數。

於是我們可以想到，我們只需要將數字與上面的數字對應即可。

1. 首先，我們要先確定高位即千位的數字，即判斷究竟是1000還是2000還是3000，於是可以想到每次將num減去1000，並加上一個”M”。

2. 然後，我們判斷百位的數字，即可以用num/100來得到百位的數字

3. 再次就是十位和個位，同2的做法

將每一個位的字母從左到右連接在一起即構成了我們的結果。

另外，在CSDN上看到一個童鞋的方法很好

I = 1;

V = 5;

X = 10;

L = 50;

C = 100;

D = 500;

M = 1000;

其中每兩個階段的之間有一個減法的表示，比如900=CM， C寫在M前面表示M-C。范圍給到3999，情況不多直接打表其實更快，用代碼判斷表示估計比較繁瑣。然後就是貪心的做法，每次選擇能表示的最大值，把對應的字符串連起來。

class Solution {
public:
    string intToRoman(int num) {
        string str;
		char *hu[] = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
		char *te[] = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
		char *on[] = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
		
		while(num>=1000) {
			str+="M";
			num-=1000;
		}
		str += hu[num/100];
		num=num%100;
		str += te[num/10];
		num=num%10;
		str+=on[num];
		return str; 
    }
};

法2:
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;
    }
}; 

法3：JAVA
class Solution {
public:
    string intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100,90, 50, 40, 10, 9, 5, 4, 1 };
        String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (number >= values[i]) {
                number -= values[i];
                result.append(numerals[i]);
            }
        }
        return result.toString();
    }
};