LeetCode Integer to Roman

LeetCode Integer to Roman

Given an integer, convert it to a roman numeral.

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


本题要求把一个阿拉伯数字转换为罗马数字。

首先要了解罗马数字的表示形式,具体看Roman numerals WIKI

roman num1 roman num2

罗马数字由上左图的7个基本字母组成,直接递归很容易求解。但是会有一些特殊情况,比如4,如果递归求解就是IIII,为了简便,采用5-1也就是IV的形式。上面右图就是基本的特殊情况。考虑特殊情况之后的递归代码如下:

class Solution {
public:
	string work(int num, string cur){
		if (num >= 1000)
			return work(num - 1000, cur + "M");
		if (num >= 500){
			if (num >= 900)
				return work(num - 900, cur + "CM");
			return work(num - 500, cur + "D");
		}
		if (num >= 100){
			if (num >= 400)
				return work(num - 400, cur + "CD");
			return work(num - 100, cur + "C");
		}
		if (num >= 50){
			if (num >= 90)
				return work(num - 90, cur + "XC");
			return work(num - 50, cur + "L");
		}
		if (num >= 10){
			if (num >= 40)
				return work(num - 40, cur + "XL");
			return work(num - 10, cur + "X");
		}
		if (num >= 5){
			if (num >= 9)
				return work(num - 9, cur + "IX");
			return work(num - 5, cur + "V");
		}
		if (num < 5){
			if (num >= 4)
				return work(num - 4, cur + "IV");
			while (num > 0){
				cur += "I";
				num--;
			}
			return cur;
		}

	}
	string intToRoman(int num) {
		return work(num, "");
	}
};

本代码提交AC,用时32MS,这么多if语句,真是不够优雅。后来看到网上一种解法,简洁漂亮许多,贴出来学习一下:

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

本代码提交AC,用时56MS,比上一版稍慢,不够这版更好看。

One thought on “LeetCode Integer to Roman

  1. Pingback: LeetCode Roman to Integer | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *