LeetCode 13 Roman to Integer：羅馬數字轉整數

題目翻譯

給定羅馬數字（範圍 1~3999），轉換為整數。

解題思路

羅馬數字規則：同符號相加，小符號在大符號左邊表示相減（如 IV=4, IX=9）。掃描字串，若當前字符值 < 下一字符值則減，否則加。

C++ 高效實現

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> mp = {
            {'I',1}, {'V',5}, {'X',10}, {'L',50},
            {'C',100}, {'D',500}, {'M',1000}
        };
        int ret = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (i + 1 < s.size() && mp[s[i]] < mp[s[i+1]])
                ret -= mp[s[i]];
            else
                ret += mp[s[i]];
        }
        return ret;
    }
};

代碼解析

• 利用 unordered_map O(1) 查字符值。
• 單次遍歷，判斷當前與下一字符大小關係決定加減。
• 時間 O(N)，空間 O(1)（映射表固定大小）。

對比

初版用枚舉 + 字串操作，效率極低。哈希表 + 單遍歷是標準最優解。