LeetCode 13 Roman to Integer（羅馬數到整型數）

LeetCode 13 Roman to Integer（羅馬數到整型數）

翻譯

給定一個羅馬數字，將其轉換到整型數值。

輸入被保證在1到3999之間。

原文

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

一開始就沒有構思好，雖然按上一題的套路可以走下去，但結果就是像我下面這樣……代碼凌亂……

public class Solution
{
    public int RomanToInt(string s)
    {
        int result = 0;
        Type R = typeof(Roman);
        string first, second;
        if (s.Length > 1)
        {
            first = s.Substring(0, 1); second = s.Substring(0, 2);
        }
        else
        {
            first = s.Substring(0, 1); second = ;
        }
        foreach (var r in Enum.GetNames(R).Reverse())
        {
            while ((r.Length == 1 && first == r) || (r.Length == 2 && second == r))
            {
                result += int.Parse(Enum.Format(R, Enum.Parse(R, r), d));
                int lenR = r.Length, lenS = s.Length;
                if (lenS - lenR < 1)
                    s = ;
                else
                    s = s.Substring(lenR, lenS - lenR);

                if (s.Length > 1)
                {
                    first = s.Substring(0, 1); second = s.Substring(0, 2);
                }
                else if (s.Length == 1)
                {
                    first = s.Substring(0, 1); second = ;
                }
                else
                {
                    first = ; second = ;
                }
            }
        }
        return result;
    }

}

public enum Roman
{
    M = 1000,
    CM = 900,
    D = 500,
    CD = 400,
    C = 100,
    XC = 90,
    L = 50,
    XL = 40,
    X = 10,
    IX = 9,
    V = 5,
    IV = 4,
    I = 1
};

雖然吧，可以運行……但是效率也太低了，簡直不忍直視……於是還是像其他大神學習學習……

下面這段代碼深深的打動了我……數組作為數組的索引……我最不常用的用法了……

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

這個算法呢，充分利用了羅馬數字兩個數字前後順序的關系，也就是說如果是I在V前面，也就是IV，它代表4，反之代表6。再搭配C++的unordered_map，可以巧妙的通過數組來進行判斷而達到對ret或加或減的目的。