LeetCode 12. 整數轉羅馬數字：規則解析、分位處理算法與 Java 實現

題目描述

給定一個整數（範圍 1~3999），將其轉換為羅馬數字表示。

羅馬數字核心規則

組合規則：

1. 相同符號最多連續出現 3 次（如 III=3，XXXX 非法）。
2. 右加左減：小值在大值右邊相加（VI=6），左邊相減（IV=4）。
3. 減法限制：僅 I、X、C 可作減數，且只能減去下一或下兩個位值（I 只減 V/X；X 只減 L/C；C 只減 D/M）。

算法思路：逐位構建法

將輸入數字按個、十、百、千四位拆解，每位獨立映射對應的羅馬符號組合，最後拼接。

核心映射表

// 每位對應 [1符號, 5符號]，千位無5符號
char[][] roman = {
    {'I', 'V'},   // 個位
    {'X', 'L'},   // 十位
    {'C', 'D'},   // 百位
    {'M',  0 }    // 千位
};

單位處理邏輯

對當前位數字 digit (0-9)：

• digit == 4：one + five（如 IV、XL、CD）
• digit == 9：one + next_one（如 IX、XC、CM）
• digit >= 5：five + (digit-5) * one（如 VIII、LXXX）
• digit < 4：digit * one（如 III、XXX）

Java 完整實現

public String intToRoman(int num) {
    if (num < 1 || num > 3999) throw new IllegalArgumentException("Out of range");

    char[][] roman = {{'I','V'}, {'X','L'}, {'C','D'}, {'M', 0}};
    StringBuilder sb = new StringBuilder();

    // 確定最高位
    int level = 0;
    for (int n = num; n > 0; n /= 10) level++;

    while (--level >= 0) {
        int digit = (num / (int)Math.pow(10, level)) % 10;
        char one = roman[level][0];
        char five = roman[level][1];

        if (digit == 4) {
            sb.append(one).append(five);
        } else if (digit == 9) {
            sb.append(one).append(roman[level+1][0]); // level+1 安全：千位digit最大3
        } else {
            if (digit >= 5) {
                sb.append(five);
                digit -= 5;
            }
            for (int i = 0; i < digit; i++) sb.append(one);
        }
    }
    return sb.toString();
}

複雜度分析

• 時間複雜度：O(1) —— 固定 4 位循環，每位常數操作。
• 空間複雜度：O(1) —— 僅使用固定大小映射表與 StringBuilder。

測試用例

替代方案：貪心查表法

int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

for (int i = 0; i < values.length; i++) {
    while (num >= values[i]) {
        num -= values[i];
        sb.append(symbols[i]);
    }
}

優點：代碼極簡，無需位運算。缺點：需維護有序表，直觀度稍低。

常見坑點

1. 未檢查輸入範圍（題目保證 1~3999，但工程代碼必須防禦）。
2. 千位處理 9 時訪問 roman[4] 越界 —— 實際上千位最大為 3，不會觸發 9，但代碼需邏輯自證或加邊界判斷。
3. 使用 String 拼接導致 O(n²) 性能，應用 StringBuilder。

GitHub 完整代碼

LeetCode Q012 Java 實現