给定一个罗马数字,将其转换到整型数值。
输入被保证在 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 或加或减的目的。
我需要好好体会了……