离线下载
PDF版 ePub版

柯于旺 · 更新于 2018-11-28 11:00:43

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<char, int> 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 或加或减的目的。

我需要好好体会了……