題目在問什麼

輸入一個整數 num，把它轉成羅馬數字字串。

題目範圍是：

  • 1 <= num <= 3999

例子

Input: num = 58
Output: "LVIII"
Input: num = 1994
Output: "MCMXCIV"

這題的關鍵

羅馬數字不是單純重複拼接而已，還有幾個特殊減法寫法：

  • IV = 4
  • IX = 9
  • XL = 40
  • XC = 90
  • CD = 400
  • CM = 900

所以不能只看每個位數要塞幾個字元，還得把這些特殊情況一起處理。

解題思路

這份寫法是用遞迴，從大位數一路往下拆：

  1. 先處理千位
  2. 再處理百位
  3. 再處理十位
  4. 最後處理個位

每個位數都先判斷特殊組合，再決定是直接追加字元，還是走一般的重複拼接。

這種寫法雖然不是最精簡的版本，但優點是規則展開得很直白，看得出每個位數在做什麼。

代碼

public class Solution
{
    public string IntToRoman(int num)
    {
        StringBuilder sb = new StringBuilder();
        Translator(num, sb);
        return sb.ToString();
    }

    void Translator(int num, StringBuilder sb)
    {
        if (num <= 0) { return; }

        if (num >= 1000)
        {
            int thousands = num / 1000;
            for (int i = 0; i < thousands; i++)
            {
                sb.Append("M");
            }
            num = num % 1000;
        }
        else if (num >= 100)
        {
            int hundreds = num / 100;
            if (hundreds == 9)
            {
                sb.Append("CM");
            }
            else if (hundreds >= 4)
            {
                if (hundreds == 4)
                {
                    sb.Append("CD");
                }
                else
                {
                    sb.Append("D");
                    for (int i = 0; i < hundreds - 5; i++)
                    {
                        sb.Append("C");
                    }
                }
            }
            else
            {
                for (int i = 0; i < hundreds; i++)
                {
                    sb.Append("C");
                }
            }
            num = num % 100;
        }
        else if (num >= 10)
        {
            int decades = num / 10;
            if (decades == 9)
            {
                sb.Append("XC");
            }
            else if (decades >= 4)
            {
                if (decades == 4)
                {
                    sb.Append("XL");
                }
                else
                {
                    sb.Append("L");
                    for (int i = 0; i < decades - 5; i++)
                    {
                        sb.Append("X");
                    }
                }
            }
            else
            {
                for (int i = 0; i < decades; i++)
                {
                    sb.Append("X");
                }
            }
            num = num % 10;
        }
        else
        {
            if (num == 9)
            {
                sb.Append("IX");
            }
            else if (num >= 4)
            {
                if (num == 4)
                {
                    sb.Append("IV");
                }
                else
                {
                    sb.Append("V");
                    for (int i = 0; i < num - 5; i++)
                    {
                        sb.Append("I");
                    }
                }
            }
            else
            {
                for (int i = 0; i < num; i++)
                {
                    sb.Append("I");
                }
            }

            num = 0;
        }

        Translator(num, sb);
    }
}

複雜度

因為數值範圍固定在 1 到 3999，這題實際上可以視為常數時間。

  • 時間複雜度：O(1)
  • 空間複雜度：O(1)，若不計輸出字串本身

這題先記住的重點

  • 關鍵不在轉換本身，而在特殊減法組合
  • 拆千、百、十、個位來處理，是很直觀的做法
  • 如果之後想再優化，可考慮改成 value-symbol 對照表的貪心寫法