凌云的博客

成功=工作+游戏+少说空话

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;
    }
};