[TOC]
P013 Roman to Integer
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 |
几个规律:
- 相同的数字连写、所表示的数等于这些数字相加得到的数、如：Ⅲ=3；
- 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如：Ⅷ=8、Ⅻ=12；
- 小的数字、（限于 Ⅰ、X 和 C）在大的数字的左边、所表示的数等于大数减小数得到的数、如：Ⅳ=4、Ⅸ=9；
- 正常使用时、连写的数字重复不得超过三次；
思路
- 从左往右扫描输入字符串
- 找到对应的字母对应的数字相加即可
- 有以上几个规律限制
- 当前处理的字符对应的数字比前一个小，正常相加即可。
- 当前处理的字符对应的数字比前一个大，加上当前数，在减去前一个数的2倍
VI==>5+1==6
VII==>5+1+1==7
IV==>1+5-2==4
代码
java
public class Solution013 {
public static int[] base = new int['X' + 1];
static {
for (int i = 0; i < base.length; i++)
base[i] = 0;
base['I'] = 1;
base['V'] = 5;
base['X'] = 10;
base['L'] = 50;
base['C'] = 100;
base['D'] = 500;
base['M'] = 1000;
}
public int romanToInt(String s) {
if (s == null || s.trim().length() == 0)
return 0;
int ret = base[s.charAt(0)];
for (int i = 1; i < s.toCharArray().length; i++) {
int current = base[s.charAt(i)];
int prev = base[s.charAt(i - 1)];
if (prev >= current)
ret += current;
else
ret += current - 2 * prev;
}
return ret;
}
public static void main(String[] args) {
Solution013 s13 = new Solution013();
String ss[] = { "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX", "X" };
for (String s : ss) {
System.out.println(s + "--->" + s13.romanToInt(s));
}
}
}
