leetcode12----------Integer to Roman

leetcode12----------Integer to Roman

Given an integer, convert it to a roman numeral.

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

羅馬數字規則：參考wiki：http://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97
1， 羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。

羅馬數字中沒有“0”。
2， 重復次數：一個羅馬數字最多重復3次。
3， 右加左減：
在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。
在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字減小數字。
4， 左減的數字有限制，僅限於I、X、C，且放在大數的左邊只能用一個。
(*) V 和 X 左邊的小數字只能用Ⅰ。
　 (*) L 和 C 左邊的小數字只能用X。
　　 (*) D 和 M 左 邊的小數字只能用C。

// LeetCode, Integer to Roman
// 時間復雜度 O(num),空間復雜度 O(1) 
class Solution{
public:
	string intToRoman(int num) {
		const int radix[] = { 1000, 900, 500, 400, 100, 90,
			50, 40, 10, 9, 5, 4, 1 };
		const string symbol[] = { "M", "CM", "D", "CD", "C", "XC",
			"L", "XL", "X", "IX", "V", "IV", "I" };
		string roman;
		for (size_t i = 0; num > 0; ++i)
		{
			int count = num / radix[i];
			num %= radix[i];
			for (; count > 0; --count) roman += symbol[i];
		}
		return roman;
	}
};