13. 罗马数字转整数
实现字符串转换规则
13.题目链接-来源:力扣(LeetCode)(简单)
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: “III”
输出: 3
思路:
这题其实可以做得比上一题巧妙,不懂为什么上题中等这题却是简单。首先转换思路比较直白,读入字符串,数值相应增加,那么跟前一题一样,需要先用个表之类的东西存储一下对应关系。难点在于,4和9的数码对应的字符串含有减法(如IX是 10 - 1 = 9,即后面的大数减去前面的小数)。
注意到,减法只会出现在大数前的小数,也就是减法永远出现在数字5,10前面的数字1处。而罗马字符整体上是从大到小显示的,一旦出现『小大』组合,便是小数变号。那么我们将字符串倒过来看,是不是就意味着,整体上是从小到大排列,一旦有『大小』组合,便是小数变号。只要此时在大数出现的时候,作一个负号标记,那么该大数往后的小数就一定需要加负号。(如MCMXCIV,倒序是VICXMCM,V是5,那么之后的I(1)就是负数,C是100,那么之后的X(10)就是负数,依此类推)
当然字符串逆序需要多一点点额外的开销,整体上原理跟官方题解没什么区别。
时间复杂度:O(1)
空间复杂度:O(1)
实现:
1 | class Solution { |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.