[LeetCode解題攻略] 13. Roman to Integer

在這篇文章中，我們將深入剖析 LeetCode 題目 13. Roman to Integer 的解題方法。這是一道經典題目，要求我們將羅馬數字轉換為整數表示。通過學習這篇教學，你將掌握如何處理羅馬數字的規則和高效地實現轉換。

題目概述

羅馬數字由以下符號組成：

規則

1. 羅馬數字通常由大到小排列，其總值是所有符號的數值之和（例如：XV = 10 + 5 = 15）。
2. 若較小的符號出現在較大的符號左側，則表示減法（例如：IV = 5 - 1 = 4）。
3. 若較小的符號出現在較大的符號右側，則表示加法（例如：VI = 5 + 1 = 6）。

範例1：

Input: s = "III"
Output: 3
Explanation: 1 + 1 + 1 = 3

範例2：

Input: s = "LVIII"
Output: 58
Explanation: 50 + 5 + 3 = 58

範例3：

Input: s = "MCMXCIV"
Output: 1994
Explanation: 1000 + 900 + 90 + 4 = 1994

解題思路

要將羅馬數字轉換為整數，我們需要遵循以下步驟：

1. 建立羅馬數字和整數的對應關係：以字典形式存儲每個羅馬數字的值。
2. 逐字檢查字符串：
3. • 若當前字符的值小於下一個字符的值，則視為減法，從總值中減去該字符的值。
   • 否則視為加法，將該字符的值加到總值中。
3. 遍歷完成後得到最終結果。

解法實現

實作 (Python)

class Solution:
    def romanToInt(self, s: str) -> int:
        # 定義羅馬數字的對應表
        roman_to_int = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        
        total = 0  # 總和
        prev_value = 0  # 前一個字符的數值

        # 從右向左遍歷字符串
        for char in reversed(s):
            current_value = roman_to_int[char]
            
            # 判斷是否需要減法
            if current_value < prev_value:
                total -= current_value
            else:
                total += current_value
            
            # 更新前一個字符的值
            prev_value = current_value

        return total        

複雜度分析

• 時間複雜度：O(n)
  我們遍歷字符串一次，其中 n 為字符串長度。
• 空間複雜度：O(1)
  僅使用固定大小的額外空間來存儲對應表和變量。

總結

本題的解題關鍵在於：

1. 理解羅馬數字的加減規則。
2. 利用反向遍歷的方式簡化處理減法的邏輯。
3. 高效實現轉換過程，時間複雜度為 O(n)。

希望這篇教學能幫助你掌握 Roman to Integer 的解法！