12. Integer to Roman

LeetCode 12. Integer to Roman

Description

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 = 4
Output: "IV"

Example 2:

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

Example 3:

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

Constraints:

• 1 <= num <= 3999

Tags

Math, String, Greedy

Solution

首先整理所有的基础的数字对应罗马字母的情况，然后由大到小检查这些数字，用num减去刚好小于等于它的数字，并把相应的罗马字母添加到结果之后，直至num == 0，最后返回结果字符串。

Collate all base-mapping from value to symbol first. Then check these values in decending order, and find a value which is just smaller than or equal to num. Subtract that value from num and append the corresponding symbol to the ans string. Repeat until num == 0.

Complexity

• Time complexity: $O(1)$

• Space complexity: $O(1)$

Code

func intToRoman(num int) string {
	var ans string
	for num > 0 {
		switch {
		case num >= 1000:
			num -= 1000
			ans += "M"
		case num >= 900:
			num -= 900
			ans += "CM"
		case num >= 500:
			num -= 500
			ans += "D"
		case num >= 400:
			num -= 400
			ans += "CD"
		case num >= 100:
			num -= 100
			ans += "C"
		case num >= 90:
			num -= 90
			ans += "XC"
		case num >= 50:
			num -= 50
			ans += "L"
		case num >= 40:
			num -= 40
			ans += "XL"
		case num >= 10:
			num -= 10
			ans += "X"
		case num >= 9:
			num -= 9
			ans += "IX"
		case num >= 5:
			num -= 5
			ans += "V"
		case num >= 4:
			num -= 4
			ans += "IV"
		case num >= 1:
			num -= 1
			ans += "I"
		}
	}
	return ans
}

Reference

1. 整数转罗马数字