LeetCode 解題思路：13. Roman to Integer（羅馬數字轉整數）

題目描述

羅馬數字包含以下七種字符：I、V、X、L、C、D 和 M。

字符          數值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，羅馬數字 2 寫做 II，即為兩個並列的 1。12 寫做 XII，即為 X + II。27 寫做 XXVII，即為 XX + V + II。

通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：

• I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9
• X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90
• C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900

給定一個羅馬數字，將其轉換成整數。

範例 1：

輸入：s = "III"
輸出：3
解釋：III = 3

範例 2：

輸入：s = "LVIII"
輸出：58
解釋：L = 50, V = 5, III = 3

範例 3：

輸入：s = "MCMXCIV"
輸出：1994
解釋：M = 1000, CM = 900, XC = 90, IV = 4

解法一：暴力解法 - 處理所有特殊情況

思路

先處理所有兩個字符的特殊組合（IV、IX、XL、XC、CD、CM），再處理單個字符。

程式碼

def romanToInt(s):
    # 定義所有可能的羅馬數字組合
    values = {
        '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
    }
    
    result = 0
    i = 0
    
    while i < len(s):
        # 檢查兩個字符的組合
        if i + 1 < len(s) and s[i:i+2] in values:
            result += values[s[i:i+2]]
            i += 2
        else:
            # 單個字符
            result += values[s[i]]
            i += 1
    
    return result

執行過程示例

s = "MCMXCIV"

i=0: "MC" 不在 values 中，處理 'M' → result = 1000, i = 1
i=1: "CM" 在 values 中 → result = 1000 + 900 = 1900, i = 3
i=3: "XC" 在 values 中 → result = 1900 + 90 = 1990, i = 5
i=5: "IV" 在 values 中 → result = 1990 + 4 = 1994, i = 7
結束：返回 1994

複雜度分析

• 時間複雜度：O(n)，n 是字串長度
• 空間複雜度：O(1)，字典大小固定

優缺點

• ✅ 邏輯直觀，容易理解
• ✅ 處理了所有特殊情況
• ❌ 需要檢查所有兩字符組合
• ❌ 程式碼較冗長

解法二：從左到右掃描（比較當前和下一個）

思路

觀察規律：當一個較小的數字在較大的數字前面時，要用減法；否則用加法。

程式碼

def romanToInt(s):
    roman_dict = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    result = 0
    
    for i in range(len(s)):
        # 如果當前字符小於下一個字符，則減去當前值
        if i < len(s) - 1 and roman_dict[s[i]] < roman_dict[s[i + 1]]:
            result -= roman_dict[s[i]]
        else:
            result += roman_dict[s[i]]
    
    return result

執行過程詳解

s = "MCMXCIV"

i=0: M(1000), 下一個是 C(100)，1000 > 100 → 加 1000
i=1: C(100), 下一個是 M(1000)，100 < 1000 → 減 100
i=2: M(1000), 下一個是 X(10)，1000 > 10 → 加 1000
i=3: X(10), 下一個是 C(100)，10 < 100 → 減 10
i=4: C(100), 下一個是 I(1)，100 > 1 → 加 100
i=5: I(1), 下一個是 V(5)，1 < 5 → 減 1
i=6: V(5), 最後一個 → 加 5

計算：1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

關鍵理解

IV = 4：I(1) < V(5)，所以 -1 + 5 = 4
VI = 6：V(5) > I(1)，所以 5 + 1 = 6
IX = 9：I(1) < X(10)，所以 -1 + 10 = 9
XI = 11：X(10) > I(1)，所以 10 + 1 = 11

複雜度分析

• 時間複雜度：O(n)
• 空間複雜度：O(1)

解法三：從右到左掃描（最優雅）

思路

從右往左掃描，如果當前數字小於前一個數字，則減去當前數字；否則加上當前數字。

程式碼

def romanToInt(s):
    roman_dict = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    result = 0
    prev_value = 0
    
    # 從右到左遍歷
    for i in range(len(s) - 1, -1, -1):
        current_value = roman_dict[s[i]]
        
        if current_value < prev_value:
            result -= current_value
        else:
            result += current_value
        
        prev_value = current_value
    
    return result

執行過程示例

s = "MCMXCIV"（從右到左）

i=6: V(5), prev=0，5 > 0 → result = 5, prev = 5
i=5: I(1), prev=5，1 < 5 → result = 5 - 1 = 4, prev = 1
i=4: C(100), prev=1，100 > 1 → result = 4 + 100 = 104, prev = 100
i=3: X(10), prev=100，10 < 100 → result = 104 - 10 = 94, prev = 10
i=2: M(1000), prev=10，1000 > 10 → result = 94 + 1000 = 1094, prev = 1000
i=1: C(100), prev=1000，100 < 1000 → result = 1094 - 100 = 994, prev = 100
i=0: M(1000), prev=100，1000 > 100 → result = 994 + 1000 = 1994

結果：1994

為什麼從右到左更優雅？

1. 不需要檢查數組邊界（不用擔心 i+1 越界）
2. 邏輯更簡單：只需要比較當前值和前一個值
3. 程式碼更簡潔

解法四：使用 replace 預處理（Python 特色）

思路

先將所有特殊的兩字符組合替換成其他符號，然後直接相加。

程式碼

def romanToInt(s):
    # 替換特殊組合
    s = s.replace("IV", "IIII")
    s = s.replace("IX", "VIIII")
    s = s.replace("XL", "XXXX")
    s = s.replace("XC", "LXXXX")
    s = s.replace("CD", "CCCC")
    s = s.replace("CM", "DCCCC")
    
    roman_dict = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    result = 0
    for char in s:
        result += roman_dict[char]
    
    return result

優缺點

• ✅ 邏輯最簡單
• ✅ 代碼易讀
• ❌ 效率較低（多次字串替換）
• ❌ 不夠優雅

解法比較

重要觀念總結

1. 羅馬數字的本質

   • 通常是從大到小排列（加法）
   • 小數在大數前面時用減法（特殊規則）

2. 演算法設計的權衡

   • 暴力解法：完整但冗長
   • 數學規律：優雅但需要洞察
   • 預處理：簡單但可能低效

3. 遍歷方向的選擇

   • 從左到右：符合閱讀習慣
   • 從右到左：避免邊界檢查

面試加分點

1. 展示多種解法：顯示思維的靈活性
2. 分析羅馬數字規律：展現問題理解能力
3. 討論邊界情況：如最大值（3999）、最小值（1）
4. 優化思路：從暴力到優雅的演進

常見錯誤

1. 忘記處理特殊組合：只考慮單個字符
2. 邊界錯誤：訪問 s[i+1] 時越界
3. 邏輯混淆：加減判斷條件寫反
4. 過度優化：使用過於複雜的數據結構

延伸思考

1. 如果要實現 Integer to Roman，該如何設計？
2. 如何驗證輸入的羅馬數字是否合法？
3. 羅馬數字系統的歷史和局限性是什麼？

掌握這道題不僅是學會轉換羅馬數字，更重要的是理解如何從問題的本質出發，設計簡潔優雅的解法！