[Leetcode]第13題Romantointeger的解法與思路

leetcode - 系列文章請點此查看!

➡️ 2: [Leetcode]第9題的Palindrome Number解法與思路

➡️ 3: 本文

題目描述
#

給定一個表示羅馬數字的字串 s，將其轉換為對應的整數。

羅馬數字規則
#

羅馬數字包含 7 種基本符號及其對應的數值：

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

組合規則
#

正常加法：較大的數字在左，較小的數字在右時，直接相加：
- ”VI” = 5 + 1 = 6
- ”MCL” = 1000 + 100 + 50 = 1150
減法規則：當較小的數字出現在較大的數字前面，代表「前者應從後者減去」：
- ”IV” = 5 - 1 = 4
- ”IX” = 10 - 1 = 9
- ”XL” = 50 - 10 = 40
- ”XC” = 100 - 10 = 90
- ”CD” = 500 - 100 = 400
- ”CM” = 1000 - 100 = 900

範例
”III” → 3 (1 + 1 + 1)
”LVIII” → 58 (50 + 5 + 3)
”MCMXCIV” → 1994 (1000 + (1000-100) + (100-10) + (5-1))

解法思路
#

方法：從右往左遍歷
#

使用字典儲存羅馬數字對應的數值。
從右向左遍歷字串：
- 若當前數值小於前一個數值，則執行「減法」。
- 否則，執行「加法」。
計算總和，輸出結果。

Python 解法
#

def romanToInt(s: str) -> int:
    # 1. 建立羅馬數字對應的字典
    roman_map = {
        ‘I ’: 1, ‘V ’: 5, ‘X ’: 10, ‘L ’: 50,
        ‘C ’: 100, ‘D ’: 500, ‘M ’: 1000
    }

    total = 0  # 最終的整數值
    prev_value = 0  # 記錄前一個數字的值

    # 2. 反向遍歷羅馬數字
    for char in reversed(s):
        current_value = roman_map[char]  # 取得當前字母對應的數值

        # 3. 若當前數字小於前一個數字，則執行減法
        if current_value < prev_value:
            total -= current_value
        else:
            total += current_value

        # 4. 更新 prev_value
        prev_value = current_value

    return total

解法解析
#

為何從右到左遍歷
#

考慮以下案例：

“MCMXCIV” (1994)
- 若從左往右處理，需先判斷 “CM”、“XC”、“IV” 這些特殊減法情況，會比較麻煩。
- 但從右往左遍歷時，每次只需比較當前值與前一個值，減少額外判斷。

如何處理減法？
#

在反向遍歷過程中：

若 current_value < prev_value，表示這是減法組合（例如 IV，I < V），則減去該數值。
否則，直接加上該數值。

例如 ”MCMXCIV“：

1.讀取 ’V‘ (5) → 加 5
2.讀取 ’I‘ (1) → 減 1（因為 I < V）
3.讀取 ’C‘ (100) → 加 100
4.讀取 ’X‘ (10) → 減 10（因為 X < C）
5.讀取 ’M‘ (1000) → 加 1000
6.讀取 ’C‘ (100) → 減 100（因為 C < M）
7.讀取 ’M‘ (1000) → 加 1000 8.
最後結果 = 1994

時間與空間複雜度
#

分析複雜度
時間複雜度 O(n) （遍歷一次字串）
空間複雜度 O(1) （使用固定大小的字典）

由於每個字母只遍歷一次，且字典查找是 O(1)。

測試
#

print(romanToInt(”III“))       # 3
print(romanToInt(”IV“))        # 4
print(romanToInt(”IX“))        # 9
print(romanToInt(”LVIII“))     # 58
print(romanToInt(”MCMXCIV“))   # 1994