羅馬數(shù)字包含以下七種字符： I蜓洪， V纤勒， X， L隆檀，C摇天，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如恐仑， 羅馬數(shù)字 2 寫(xiě)做 II 泉坐，即為兩個(gè)并列的 1。12 寫(xiě)做 XII 菊霜，即為 X + II 坚冀。 27 寫(xiě)做 XXVII, 即為 XX + V + II 。
通常情況下鉴逞，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊记某。但也存在特例，例如 4 不寫(xiě)做 IIII构捡，而是 IV液南。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 勾徽。同樣地滑凉，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
- I 可以放在 V (5) 和 X (10) 的左邊，來(lái)表示 4 和 9畅姊。
- X 可以放在 L (50) 和 C (100) 的左邊咒钟，來(lái)表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左邊若未，來(lái)表示 400 和 900朱嘴。
給定一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字粗合。輸入確保在 1 到 3999 的范圍內(nèi)萍嬉。
示例 4:
輸入: 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
解法一
沒(méi)看答案之前的做法，暴力求解法隙疚。
主要思路：從個(gè)位開(kāi)始壤追，遍歷出每一位，然后根據(jù)各種情況再表示出來(lái)供屉，并拼接到返回的字符串上行冰。
# ['I', 'V', 'X', 'L', 'C', 'D', 'M']
# [1, 5, 10, 50, 100, 500, 1000]
def handleNum(cur, ns):
if cur < 4:
ns = 'I' * cur + ns
elif cur == 4:
ns = 'IV' + ns
elif cur == 5:
ns = 'V' + ns
elif cur < 9:
ns = 'V' + 'I' * (cur - 5) + ns
elif cur == 9:
ns = 'IX' + ns
elif cur < 40:
ns = 'X' * (cur // 10) + ns
elif cur == 40:
ns = 'XL' + ns
elif cur == 50:
ns = 'L' + ns
elif cur < 90:
ns = 'L' + 'X' * (cur // 10 - 5) + ns
elif cur == 90:
ns = 'XC' + ns
elif cur < 400:
ns = 'C' * (cur // 100) + ns
elif cur == 400:
ns = 'CD' + ns
elif cur == 500:
ns = 'D' + ns
elif cur < 900:
ns = 'D' + 'C' * (cur // 100 - 5) + ns
elif cur == 900:
ns = 'CM' + ns
elif cur < 4000:
ns = 'M' * (cur // 1000) + ns
return ns
# 先從個(gè)位開(kāi)始，表示每一位贯卦，再拼接起來(lái)
ns, div = "", 10
while True:
# 這一位的數(shù)
cur = num % div
ns = handleNum(cur, ns)
# 將這位去掉過(guò)后的整數(shù)
num = num // div * div
div *= 10
# 最后一位资柔，計(jì)算出來(lái)就結(jié)束了
if num // div == 0:
cur = num
ns = handleNum(cur, ns)
break
return ns
解法二
參考力扣官方答案焙贷，采用貪心算法撵割，貪心算法是一種在當(dāng)前時(shí)間做出最佳可能決策的算法。這里既是取出最大可能的符合辙芍。
主要思想：為了表示一個(gè)給定的整數(shù)啡彬，我們尋找適合它的最大符號(hào)。我們減去它故硅，然后尋找適合余數(shù)的最大符號(hào)庶灿，依此類(lèi)推，直到余數(shù)為0吃衅。我們?nèi)〕龅拿總€(gè)符號(hào)都附加到輸出的羅馬數(shù)字字符串上往踢。
def intToRoman2(num):
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")]
# 記錄羅馬數(shù)字符號(hào)
roman_digits = []
# 從最大到最小循環(huán)遍歷每個(gè)符號(hào)，檢查當(dāng)前符號(hào)的有多少個(gè)副本適合剩余的整數(shù)
for value, symbol in digits:
# 當(dāng)數(shù)字取完了過(guò)后就結(jié)束遍歷
if num == 0: break
# Return the tuple (x//y, x%y)
count, num = divmod(num, value)
# 將這位表示的羅馬數(shù)字符號(hào)添加到數(shù)組里面
roman_digits.append(symbol * count)
# 返回拼接起來(lái)的字符串
return "".join(roman_digits)
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(1)徘层。由于有一組有限的羅馬數(shù)字峻呕，循環(huán)可以迭代多少次有一個(gè)硬上限。因此趣效，我們說(shuō)時(shí)間復(fù)雜度是常數(shù)的瘦癌，即 O(1)。
- 空間復(fù)雜度：O(1)跷敬，使用的內(nèi)存量不會(huì)隨輸入整數(shù)的大小而改變讯私，因此是常數(shù)的。
解法三
參考力扣官方答案，將每一位都表示出來(lái)斤寇，然后再逐位進(jìn)行計(jì)算和我的解法一有點(diǎn)相像桶癣。
主要思想：在代碼中實(shí)現(xiàn)它最簡(jiǎn)單的方法是使用 4 個(gè)獨(dú)立的數(shù)組；每個(gè)位置值對(duì)應(yīng)一個(gè)數(shù)組娘锁。然后鬼廓，在輸入數(shù)字中提取每個(gè)位置的數(shù)字，在相關(guān)數(shù)組中查找它們的符號(hào)致盟，并將它們?nèi)扛郊釉谝黄稹?/p>
def intToRoman3(num):
thousands = ["", "M", "MM", "MMM"]
hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
return thousands[num // 1000] + hundreds[num % 1000 // 100] + tens[num % 100 // 10] + ones[num % 10]
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(1)碎税。無(wú)論輸入的大小，都會(huì)執(zhí)行相同數(shù)量的操作馏锡。因此雷蹂，時(shí)間復(fù)雜度是常數(shù)的。
- 空間復(fù)雜度：O(1)杯道，雖然我們使用數(shù)組匪煌，但不管輸入的大小，它們都是相同的大小党巾。因此萎庭，它們是常數(shù)級(jí)空間。
