題目鏈接：國(guó)際版鱼炒，國(guó)內(nèi)版
公司：Meta
解法：貪心
題目描述
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 = 3
Output: "III"
Explanation: 3 is represented as 3 ones.
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.
思路
題目很容易理解，把阿拉伯?dāng)?shù)字轉(zhuǎn)換成羅馬數(shù)字窍仰，難點(diǎn)在于羅馬數(shù)字中的 4 和 9 需要由另外兩個(gè)羅馬數(shù)字 5（10）和 1 組合而成篙程。不過(guò)我們也可以發(fā)現(xiàn)，羅馬數(shù)字中比較特殊的組合一共只有 6 種：4,9,40,90,400,900云茸。我們可以把這些特殊的數(shù)字組合當(dāng)成羅馬數(shù)字中本來(lái)就有的基礎(chǔ)數(shù)字蜓堕，按照數(shù)值從大到小的順序?qū)戇M(jìn) list 中墨叛，之后采用貪心的策略從頭遍歷這個(gè) list 即可。
代碼參考
class Solution:
def intToRoman(self, num: int) -> str:
# Greedy, T: O(1), S: O(1)
digits = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
roman_digits = []
for value, symbol in digits:
if num == 0:
break
count, num = divmod(num, value)
roman_digits.append(symbol * count)
return ''.join(roman_digits)
