13. Roman to Integer

Easy

Description

給定一個羅馬數字字串 s，將其轉換為整數。羅馬數字由 I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000) 組成，有六種減法規則（如 IV=4、IX=9 等）。

Example:

Input: s = “MCMXCIV” Output: 1994 (M=1000, CM=900, XC=90, IV=4)

Intuition#

核心思路：從左到右遍歷，若當前字元代表的值小於下一個字元的值，則減去當前值（減法規則），否則加上。

羅馬數字通常從大到小排列，直接累加
遇到減法情況（如 IV、IX）時，較小的數字在前面
規律：若當前值 < 下一個值，則該值要被減去

Approaches#

1: 查表法（兩字元優先）#

概念: 優先匹配兩字元的減法組合，匹配不到再用單字元
時間複雜度: O(n)
空間複雜度: O(1) - 查表大小固定

class Solution {
    fun romanToInt(s: String): Int {
        val map = mapOf(
            "M" to 1000, "CM" to 900, "D" to 500, "CD" to 400,
            "C" to 100, "XC" to 90, "L" to 50, "XL" to 40,
            "X" to 10, "IX" to 9, "V" to 5, "IV" to 4, "I" to 1
        )
        var result = 0
        var i = 0
        while (i < s.length) {
            if (i + 1 < s.length && map.containsKey(s.substring(i, i + 2))) {
                result += map[s.substring(i, i + 2)]!!
                i += 2
            } else {
                result += map[s.substring(i, i + 1)]!!
                i++
            }
        }
        return result
    }
}

⭐2: 比較前後大小#

概念: 若當前值小於下一個值則減，否則加——一行規則涵蓋所有情況
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun romanToInt(s: String): Int {
        val map = mapOf(
            'I' to 1, 'V' to 5, 'X' to 10, 'L' to 50,
            'C' to 100, 'D' to 500, 'M' to 1000
        )
        var result = 0
        for (i in s.indices) {
            val curr = map[s[i]]!!
            val next = if (i + 1 < s.length) map[s[i + 1]]!! else 0
            result += if (curr < next) -curr else curr
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 比較相鄰元素決定加或減——簡潔地處理了所有減法規則
關鍵技巧: if (curr < next) -curr else curr 這個判斷涵蓋了所有六種減法情況，無需逐一列舉