Leetcode: Roman to Integer
Leetcode: Roman to Integer
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 16:03:27
发布于 2019-01-22 16:03:27
题目： Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
由于不知道罗马数字和阿拉伯数字的转换规则，先百度之。 下面的关于罗马数字的说明来自百度百科：
基本字符 | I | V | X | L | C | D | M |
|---|---|---|---|---|---|---|---|
相应的阿拉伯数字表示为 | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
下面是转换规则： 1、相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3； 2、小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12； 3、小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9； 4、正常使用时，连写的数字重复不得超过三次。 5、在一个数的上面画一条横线，表示这个数扩大1000倍。
思路分析： 因为题目中注明数字从1到3999，所以第5条用不上。当数字小于3999的时候，我们可以这样计算：从前向后遍历罗马数字，如果某个数比前一个数小，则加上该数。反之，减去前一个数的两倍然后加上该数 。（为什么右边小于左边的时候要减去2倍呢？那是因为你原来遍历的时候已经加过一遍了，本来要减去的，所以现在要减去2倍。）
C++参考代码：
class Solution
{
public:
int getRomanNumber(char ch)
{
switch (ch)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
int romanToInt(string s)
{
string::size_type length = s.length();
if (length < 1) return 0;
int number = getRomanNumber(s[0]);
int previous = number;//前一个字符
int current = number;//当前字符
for (size_t i = 1; i < length; i++)
{
previous = current;
current = getRomanNumber(s[i]);
if (previous >= current)
{
number += current;
}
else
{
number += current - 2 * previous;
}
}
return number;
}
};C#参考代码：
public class Solution
{
public int GetRomanNumber(char ch)
{
switch (ch)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
public int RomanToInt(string s)
{
if (s.Length < 1) return 0;
int number = GetRomanNumber(s[0]);
int previous = number;
int current = number;
for (int i = 1; i < s.Length; i++)
{
previous = current;
current = GetRomanNumber(s[i]);
if (previous >= current)
{
number += current;
}
else
{
number += current - 2 * previous;
}
}
return number;
}
}Python参考代码： Python中我没有使用函数的形式返回单个字符对于的阿拉伯数字，直接使用了一个dict保存了键值对。
class Solution:
# @return an integer
def romanToInt(self, s):
length = len(s)
if length < 1:
return 0
romanDict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
number = romanDict[s[0]]
previous = number
current = previous
for i in range(1, length):
previous = current
current = romanDict[s[i]]
if previous >= current:
number = number + current
else:
number = number + current - 2 * previous
return number本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月22日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读