LeetCode Integer to Roman 整數轉羅馬數字：三種解法對比

LeetCode Integer to Roman：整數轉羅馬數字的三種高效解法

羅馬數字轉換規則：I=1, V=5, X=10, L=50, C=100, D=500, M=1000，特殊減法表示：IV=4, IX=9, XL=40, XC=90, CD=400, CM=900。輸入範圍 1~3999。本文展示三種解法：位權分解法、貪心查表法、Java 版本。

解法一：位權分解法（直觀高效）

按千、百、十、個位分別查表拼接。利用預計算字符串數組，O(1) 時間複雜度。

class Solution {
public:
    string intToRoman(int num) {
        string res;
        const char* thousands[] = {"", "M", "MM", "MMM"};
        const char* hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        const char* tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        const char* ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

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

解法二：貪心查表法（通用性強）

按值從大到小排序符號與數值，每次減去最大可能值，拼接對應符號。易擴展至更大範圍。

class Solution {
public:
    string intToRoman(int num) {
        string res;
        vector sym = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        vector val = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        for (int i = 0; num > 0; ++i) {
            while (num >= val[i]) {
                num -= val[i];
                res += sym[i];
            }
        }
        return res;
    }
};

解法三：Java 版本

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] numerals = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                res.append(numerals[i]);
            }
        }
        return res.toString();
    }
}

複雜度與選擇建議

• 解法一：固定 4 次查表，分支最少，實際運行最快，適合固定範圍 1~3999。
• 解法二/三：邏輯統一，易維護、易擴展，適合面試現場編寫。
• 時間複雜度均為 O(1)（符號數量有限），空間 O(1)。