Leetcode Roman To Integer

Leetcode Roman To Integer

日常刷题。经典的找规律题,看起来很复杂,找到规律了就很好做了。

https://leetcode-cn.com/problems/roman-to-integer/

一、题目

罗马数字包含以下七种字符: I,V,X,L,C,D 和 M。

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  1. I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  2. X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  3. C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1

示例 2

示例 3

示例 4

示例 5

二、解决方案

很多同学一看这题,这么多规则,直接就被吓跑/去看答案了。实际上我们要冷静,先看看这题的难度。如果是hard,请马上关闭Leetcode。

结果发现,这题居然是easy,这就意味着一定有明显规则,只要发现了即可解题。

我的初步思路:

  1. 所谓的“罗马数字”,其实就是一堆字符串,代表着一堆数字。
  2. “罗马数字”的排列,一定存在着某种规则,可以稳定计算,否则不会出这道题。

接下来仔细观察例子:

  1. 实例一为“III”,结果为3。这就意味着,如果一个罗马数字和后面的罗马数字相等,可以直接相加。
  2. 实例二为“IV”,结果为4。可以看出,如果第一个罗马数字比后面的罗马数字要小,那么结果为后面的数字 – 前面的数字,转换一下,为 -前面的数字 + 后面的数字。
  3. 通过实例三,可以进一步验证实例二的结论,“IX”结果为 -1 + 10,等到9。
  4. 实例四为“LVIII”,结果为58。简单分解一下,可以发现是“L” + “V” + “III”,即50 + 5 + 3。可以发现,如果“L” > “V”,那么算式就是“L” + “V”。也就是说,如果前面的数字比后面的数字大,结果就是前面的数字 + 后面的数字。
  5. 总结上面所有规律,如有ab,可得:1、a >= b,ab = a + b。2、 a < b,ab = -a + b。此题的规律在于当前数字向后比较。
  6. 最后用实例六验证上面的规律:“MCMXCIV”为 1000 – 100 + 1000 – 10 + 100 – 1 + 5 = 1994 ,结果证明了我们的猜想。

得出最终算法:

  1. 用HashMap映射字符和数字。
  2. 从头解析字符串,进行数字的计算。
  3. ab,即a和b比较。如果a >= b,直接+a,b暂时不管。
  4. bc,即b和c比较。如果b < c,直接-b,c暂时不管。
  5. 假如c为最后一位,那么直接+c。

最终代码为:

RomanToInteger.java

结果为:

其实一般不会用“VV”来代表10,因为直接有“X”…但是结果依然是对的,因为规则如此。

三、总结

这题真的没什么好说的。以后做题先看看难度,不要被文字量吓跑了。

发布者

xie4ever

发表评论

电子邮件地址不会被公开。