應用題 從阿拉伯數字轉成羅馬數字 Leetcode 12: Integer to Roman

Anne Nygård on Unsplash

這題的題目在這裡:

題目會給定我們一組十進位表示法的阿拉伯數字，要求我們把它轉換為對應的羅馬數字。

測試範例

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.

約束條件

Constraints:

• 1 <= num <= 3999

演算法

把原本題目給的羅馬數字和十進位數字的關係建立成一張映射表(字典)。

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

把每一個羅馬數字由大到小排列，當作基底，做數字的轉換。

每一輪除法留下來的商數就是對應羅馬數字所需要的係數，餘數帶入下一輪轉換，一直反覆進行，直到個位數為止。

程式碼

class Solution:
　def intToRoman(self, num: int) -> str:
　　
		## dictionary:
		# key: decimal value as base
		# value: corresponding roman symbol
　　mapping_table = {
　　　　　　　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_string = ''
　　
		# represent input num in roman number system
　　for base, roman_symbol in mapping_table.items():
　　　
			# update roman string with corresponding roman symbol
　　　roman_string += (num // base) * roman_symbol
　　　
			# update num as remainder
　　　num = num % base
　　
		
　　return roman_string

複雜度分析

時間複雜度: O( 1)
從左到右，每個羅馬數字對應的基底掃描過一遍。

空間複雜度: O(1)
都是臨時變數，所占用的記憶體空間為常數級別O(1)

關鍵知識點

想到用字典(雜湊映射表)，去儲存每個羅馬數字和十進位表示裡面對應到的阿拉伯數字的映射關係。

​本題有一個對稱的兄弟姊妹題 Roman to Integer，可以互相做為學習、比較的參照。

Reference:

[1] Python/C++ by mapping and math [w/ Comment] - Integer to Roman - LeetCode