[数据结构与算法]leetcode每日一题-13:罗马数字转整数

leetcode每日一题-13:罗马数字转整数

链接

罗马数字转整数

题目

分析

这个题总体上来说是一个遍历题目。我们遍历每一位看看当前字母应该转化成什么阿拉伯数字，唯一需要注意的就是题目中给出的三种特殊的双字符组合构成数据的方式，但是这也很容易处理，每次我们遍历到I,X,C,这个几个字母的时候，查看一下后方是不是相应的组合字符即可。然后累计所有值就是答案。

代码

C++

class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        int len = s.size();
        for(int i=0 ; i<len ; i++)
        {
            // cnt用来表示当前数位所表示的阿拉伯数字
            int cnt;
            // 如果当前字符是I就查看下一位是什么
            if(s[i] == 'I')
            {
                // 首先要判断下一位存在不存在
                int idx = i + 1;
                if(idx < len)
                {
                    // 如果下一位是可以构成组合的字符，那么我们就更新当前的cnt值，并把i多往后移动一位
                    if(s[idx] == 'V') cnt = 4, i++;
                    else if(s[idx] == 'X') cnt = 9, i++;
                    else cnt = 1;
                }
                else cnt = 1;
            }
            else if(s[i] == 'V') cnt = 5;
            else if(s[i] == 'X')
            {
                // 针对X也是同理，进行判断
                int idx = i + 1;
                if(idx < len)
                {
                    if(s[idx] == 'L') cnt = 40, i++;
                    else if(s[idx] == 'C') cnt = 90, i++;
                    else cnt = 10;
                }
                else cnt = 10;
            }
            else if(s[i] == 'L') cnt = 50;
            else if(s[i] == 'C')
            {
                // 针对C也是同理，进行判断
                int idx = i + 1;
                if(idx < len)
                {
                    if(s[idx] == 'D') cnt = 400, i++;
                    else if(s[idx] == 'M') cnt = 900, i++;
                    else cnt = 100;
                }
                else cnt = 100;
            }
            else if(s[i] == 'D') cnt = 500;
            else if(s[i] == 'M') cnt = 1000;

            // 累计每个数位的值即可
            res += cnt;
        }
        return res;
    }
};

Java

官方的题解更为简洁，但是道理是同样的道理。

class Solution {
    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    public int romanToInt(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
}

作者：LeetCode-Solution