【LeetCode】13. Roman to Integer

LeetCode-13

Links:https://leetcode.com/problems/roman-to-integer/

Given a roman numeral, convert it to an integer.

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

题目大意：给出一个罗马数字，转换成整数。
数据范围在1-3999之间

解析：
Roman numeral 的规则是：采用七个罗马字母作数字、即Ⅰ（1）、X（10）、C（100）、M（1000）、V（5）、L（50）、D（500）。
记数的方法：
1.相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3;

2.小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12;

3.小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9;

4.在一个数的上面画一条横线，表示这个数增值 1,000 倍，如=5000。

思路：根据Roman计数方法：采用从后向前遍历。如果相等或更大则记录最大值，且加上。如果比最大值小，则减去即可。
例如：”MCMXCVI”
1+5+100-10+1000-100+1000 = 1996

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

class Solution {

public:

int romanToInt(string s) {

map<char,int>roman;

roman['I'] = 1;

roman['V'] = 5;

roman['X'] = 10;

roman['L'] = 50;

roman['C'] = 100;

roman['D'] = 500;

roman['M'] = 1000;

int ans = 0;

int temp = 1;

for(int i=s.size()-1;i>=0;i--)

{

if(roman[s[i]] >= temp){

ans += roman[s[i]];

temp = roman[s[i]];

}

else {

ans -= roman[s[i]];

}

return ans;

}

};

【LeetCode】13. Roman to Integer

Tagged on: LeetCode