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倍
1
2
3
VI==>5+1==6
VII==>5+1+1==7
IV==>1+5-2==4

代码

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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));
		}
	}
}