[LeetCode 解题报告]013. Roman to Integer

71 阅读 0 评论 47 点赞

我是靠谱客的博主孤独白猫，最近开发中收集的这篇文章主要介绍[LeetCode 解题报告]013. Roman to Integer，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description：

Given a roman numeral, convert it to an integer.

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

解题思路：这道题是 [LeetCode 解题报告]011. Integer to Roman 逆问题，讲罗马数字转化成阿拉伯数字。

下面用例子说明该题的考察点：

罗马数字 IV 对应的阿拉伯数字为 4 相当于5 - 1 = 4
罗马数字 VI 对应的阿拉伯数字为 6 相当于6 + 1 = 7
罗马数字 IX 对应的阿拉伯数字为 9 相当于 10 - 1 = 9
罗马数字 XIV 对应的阿拉伯数字为14 相当于 10 - 1 + 5 = 14
...... 是不是发现规律了？

算法思想：

步骤1. I 对应 1， V 对应 5， X 对应 10， L 对应 50， C 对应 100， D 对应 500， M 对应 1000； s就是有IVXLCDM这些字符组合而成。用p指向s中第一个字符，q指向s中第二个字符，用ans保存结果。

步骤2. 如果p指向字符对应的数值比q指向的大，则将p指向字符所对应的数值加到ans中；否则，从ans中减去p指向字符所对应数值。更新p和q（即p++，q++）,重复执行步骤2，直到q指向最后一个字符。

步骤3. 对于最后一个字符，将其对应的数值加到ans中。

在这里我们使用STL中的map映照容器。建立罗马字符与阿拉伯数字之间的关系。关于map映照容器的介绍请参考[C++ 从入门到放弃-05]C++STL之map映照容器

class Solution {
public:
    int romanToInt(string s) {
        
        int res = 0;
        int len = s.length() - 1;
        map<char, int> m;
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        
        for(int i = 0; i < len; i ++) {
            if(m[s[i]] >= m[s[i+1]])
                res = res + m[s[i]];
            else
                res = res - m[s[i]];
        }
        return res + m[s[len]];
    }
};