在這篇文章中，我們將深入剖析 LeetCode 題目 13. Roman to Integer 的解題方法。這是一道經典題目，要求我們將羅馬數字轉換為整數表示。通過學習這篇教學，你將掌握如何處理羅馬數字的規則和高效地實現轉換。
題目概述
羅馬數字由以下符號組成：
規則
- 羅馬數字通常由大到小排列，其總值是所有符號的數值之和（例如：
XV = 10 + 5 = 15）。 - 若較小的符號出現在較大的符號左側，則表示減法（例如：
IV = 5 - 1 = 4）。 - 若較小的符號出現在較大的符號右側，則表示加法（例如：
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
解題思路
要將羅馬數字轉換為整數，我們需要遵循以下步驟：
- 建立羅馬數字和整數的對應關係：以字典形式存儲每個羅馬數字的值。
- 逐字檢查字符串：
- 若當前字符的值小於下一個字符的值，則視為減法，從總值中減去該字符的值。
- 否則視為加法，將該字符的值加到總值中。
- 遍歷完成後得到最終結果。
解法實現
實作 (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)
僅使用固定大小的額外空間來存儲對應表和變量。
總結
本題的解題關鍵在於：
- 理解羅馬數字的加減規則。
- 利用反向遍歷的方式簡化處理減法的邏輯。
- 高效實現轉換過程，時間複雜度為 O(n)。
希望這篇教學能幫助你掌握 Roman to Integer 的解法！
