凌云的博客

行胜于言

LeetCode 算法题 13. Roman to Integer

分类:algorithm| 发布时间:2016-07-02 00:29:00


题目

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

题意

将罗马数字数字转换为整形。

解法

这个比较简单,主要是要了解罗马数字的规则。

Wikipedia: Roman numerals

从左到右扫描字符串,若右邻字符比当前字符大,则减去当前字符所代表的值, 否则加上当前字符所代表的值。

class Solution {
public:
	int romanToInt(string s) {
		if (s.empty()) {
			return 0;
		}

		int romans[24];
		romans['I' - 'A'] = 1;
		romans['V' - 'A'] = 5;
		romans['X' - 'A'] = 10;
		romans['L' - 'A'] = 50;
		romans['C' - 'A'] = 100;
		romans['D' - 'A'] = 500;
		romans['M' - 'A'] = 1000;

		int result = 0;
		int cur = romans[s[0] - 'A'], right = 0;
		const int size = s.size();

		for (int i = 1; i != size; ++i) {
			right = romans[s[i] - 'A'];
			if (cur < right) {
				result -= cur;
			} else {
				result += cur;
			}

			cur = right;
		}

		result += cur;
		return result;
	}
};