LeetCode 羅馬數字轉整數：規則解析與單遍歷算法

題目與規則

給定合法羅馬數字字符串（1~3999），轉為整數。核心規則：

• 基本符號：I=1, V=5, X=10, L=50, C=100, D=500, M=1000
• 左減規則：較小符號在較大符號左側表示減法（IV=4, IX=9, XL=40...）
• 其餘情況累加

單遍歷貪心算法

從左向右掃描，維護 val = map[ch[i]]：

• 若 i 是最後一字符，或下一字符值 ≤ 當前值 → num += val
• 否則（下一字符值 > 當前值，構成左減對）→ num -= val

這相當於：正常累加，遇到左減對時把前一個符號「撤銷」並改為減法。

Java 實現

public int romanToInt(String s) {
    Map<Character, Integer> romans = Map.of(
        'I',1, 'V',5, 'X',10, 'L',50, 'C',100, 'D',500, 'M',1000);
    int num = 0;
    for (int i = 0; i < s.length(); i++) {
        int val = romans.get(s.charAt(i));
        if (i == s.length()-1 || romans.get(s.charAt(i+1)) <= val)
            num += val;
        else
            num -= val;
    }
    return num;
}

複雜度與驗證

• 時間 O(n)，空間 O(1)（映射表固定大小）。
• 測例："MCMXCIV" → 1994（M=1000, CM=900, XC=90, IV=4）。

擴展：整數轉羅馬數字

反向操作可用「貪心查表法」：預設值符號對按值降序排列（1000:M, 900:CM, 500:D, 400:CD...），循環減去最大可能值並拼接符號，同樣 O(1) 時間（因最大 3999）。