12. Integer to Roman

Medium

Description

給定一個整數 num（1 <= num <= 3999），將其轉換為羅馬數字字串。

Example:

Input: num = 1994 Output: “MCMXCIV” (M=1000, CM=900, XC=90, IV=4)

Intuition#

核心思路：貪心法——從最大面額開始，盡量用大的符號表示，包含六個減法組合（CM、CD、XC、XL、IX、IV）。

羅馬數字有 13 種基本表示（7 個標準 + 6 個減法組合）
從大到小排列，每次取最大的可用符號，直到 num 為 0
這是典型的貪心策略

Approaches#

⭐1: 貪心查表#

概念: 建立值-符號對照表（從大到小），每次盡量多用最大符號
時間複雜度: O(1) - num 最大 3999，迴圈次數有上界（約 15 次）
空間複雜度: O(1) - 結果字串長度有上界

class Solution {
    fun intToRoman(num: Int): String {
        val values = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
        val symbols = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")

        val sb = StringBuilder()
        var n = num
        for (i in values.indices) {
            while (n >= values[i]) {
                sb.append(symbols[i])
                n -= values[i]
            }
        }
        return sb.toString()
    }
}

2: 硬編碼各位數#

概念: 將千位、百位、十位、個位分別對應的羅馬數字列舉出來，直接查表
時間複雜度: O(1)
空間複雜度: O(1)

class Solution {
    fun intToRoman(num: Int): String {
        val thousands = arrayOf("", "M", "MM", "MMM")
        val hundreds = arrayOf("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
        val tens = arrayOf("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
        val ones = arrayOf("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")

        return thousands[num / 1000] + hundreds[num % 1000 / 100] +
               tens[num % 100 / 10] + ones[num % 10]
    }
}

🔑 Takeaways#

Pattern: 貪心選擇最大面額——與找零錢問題類似
關鍵技巧: 把 6 個減法組合（CM, CD, XC, XL, IX, IV）也放入查表中，就不需要特殊處理減法規則