[LeetCode解題攻略] 12. Integer to Roman

在這篇文章中，我們將探討 LeetCode 題目 12. Integer to Roman 的解題方法。這是一道經典的模擬題，要求我們將整數轉換為羅馬數字表示。通過這篇文章，你將學會如何高效地解決這道題，並理解羅馬數字的基本規則和轉換技巧。

題目概述

羅馬數字由以下符號組成：

羅馬數字規則

• 通常情況下，數字按照從大到小的順序排列。
• 如果一個較小的數字出現在較大的數字前，則表示減法（如：IV = 4, IX = 9）。
• 如果一個較小的數字出現在較大的數字後，則表示加法（如：VI = 6, XI = 11）。

範例1：

Input: num = 3749
Output: "MMMDCCXLIX"
Explanation: 
3749 = 3000 + 700 + 40 + 9
= "MMM" + "DCC" + "XL" + "IX"
= "MMMDCCXLIX"

範例2：

Input: num = 58
Output: "LVIII"
Explanation: 
58 = 50 + 8
= "L" + "VIII"
= "LVIII"

範例3：

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

思路分析

我們需要將給定的整數轉換為羅馬數字，這可以通過以下方法實現：

1. 構建一個對應表，存儲羅馬數字和它們的值（如：1000 -> "M"，900 -> "CM" 等）。
2. 按照從大到小的順序，逐步將數字減去能被最大數值整除的部分，並將對應的羅馬數字添加到結果中。
3. 持續迭代，直到數字變為零。

這種方法確保我們能夠正確地處理所有可能的數字組合。

解法實現

實作 (Python)

class Solution:
    def intToRoman(self, num: int) -> str:
        # 定義羅馬數字的值與符號對應表
        value_symbols = [
            (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")
        ]
        
        result = []
        
        # 迭代每個數值與符號
        for value, symbol in value_symbols:
            # 計算當前符號可以出現的次數
            while num >= value:
                num -= value
                result.append(symbol)
        
        # 將結果列表轉為字串
        return "".join(result)

複雜度分析

• 時間複雜度：O(1)
  常數級別的操作，因為數字最大為 3999，對應的羅馬數字轉換步驟是固定的。
• 空間複雜度：O(1)
  僅使用固定的對應表和結果字符串。

總結

這道題的關鍵在於熟悉羅馬數字的規則和表示方式，並通過構建從大到小的對應表來模擬轉換過程。使用這種貪心策略，能夠高效地完成數字到羅馬數字的轉換。