[LeetCode]Roman to Integer

这题只要知道罗马数字是怎么表示的就不难，十以内的数字举例。1,4,5,9都会特殊表示(I, IV, V, IX)，剩下的比如说7，就会表示成5+2的形式(VII)，那么对于一个十以内的数字，要把它表示成罗马数字，只需要用贪婪的思想，从目标数中减去1,4,5,9中小于等于目标数的最大值，直到目标数变为零，这和把一个数表示成二进制的思路类似。任意十以内的数必定可以表示成这四个数的线性组合: x * 1 + y * 4 + z * 5 + k * 9(x <= 3, y,z,k <= 1)，并且表达式唯一，这也说明了我们用贪婪的做法确定xyzk的值的正确性。对于十以上的数也是同理。
代码如下：

	class Solution {
	public:
	string intToRoman(int num) {
	vector<string> romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
	vector<int> nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
	string res = "";
	for(int i = 0; i < romans.size(); ++i)
	{
	while(num >= nums[i])
	{
	num -= nums[i];
	res += romans[i];
	}
	}
	return res;
	}
	};

view raw inttoroman.cpp hosted with ❤ by GitHub