`
SunnyYoona
  • 浏览: 361768 次
社区版块
存档分类
最新评论

[LeetCode]13.Roman to Integer

 
阅读更多

【题目】

Given a roman numeral, convert it to an integer.

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

【分析】

这是一种首先会想到的思路:一个一个字母解析,先解析是不是双字母罗马数字,如果不是就按单字母罗马数字解析。

【代码】

/*********************************
*   日期:2015-01-22
*   作者:SJF0115
*   题目: 13.Roman to Integer
*   网址:https://oj.leetcode.com/problems/roman-to-integer/
*   结果:AC
*   来源:LeetCode
*   博客:
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        int result = 0;
        int len = s.length();
        if(len <= 0){
            return result;
        }//if
        for(int i = 0;i < len;++i){
            if(s[i] == 'M'){
                result += 1000;
            }//if
            else if(s[i] == 'D'){
                result += 500;
            }
            else if(s[i] == 'C'){
                if(s[i+1] == 'M'){
                    result += 900;
                    ++i;
                }//if
                else if(s[i+1] == 'D'){
                    result += 400;
                    ++i;
                }
                else{
                    result += 100;
                }
            }
            else if(s[i] == 'L'){
                result += 50;
            }
            else if(s[i] == 'X'){
                if(s[i+1] == 'C'){
                    result += 90;
                    ++i;
                }//if
                else if(s[i+1] == 'L'){
                    result += 40;
                    ++i;
                }
                else{
                    result += 10;
                }
            }
            else if(s[i] == 'V'){
                result += 5;
            }
            else if(s[i] == 'I'){
                if(s[i+1] == 'X'){
                    result += 9;
                    ++i;
                }
                else if(s[i+1] == 'V'){
                    result += 4;
                    ++i;
                }
                else{
                    result += 1;
                }
            }
        }//for
        return result;
    }
};

int main(){
    Solution solution;
    string roman = "XCVIII";
    int result = solution.romanToInt(roman);
    // 输出
    cout<<result<<endl;
    return 0;
}

【分析二】

在一个较大的罗马数字的右边记上一个较小的罗马数字,表示大数字加小数字。在一个较大的数字的左边记上1个较小的罗马数字,表示大数字减小数字。

可以通过判断相邻两个数的大小来计算

【代码二】

class Solution {
public:
    int romanToInt(string s) {
        int result = 0;
        int len = s.length();
        if(len <= 0){
            return result;
        }//if
        int value[] = {1000,500,100,50,10,5,1};
        // 转换
        int i;
        for(i = 0;i < len-1;++i){
            int index = FindIndex(s[i]);
            int index2 = FindIndex(s[i+1]);
            // 相邻左边下标大于等于右边下标
            if(index <= index2){
                result += value[index];
            }
            // 相邻左边下标小于右边下标
            else{
                result += value[index2] - value[index];
                ++i;
            }
        }//for
        if(i != len){
            // 最后一个元素
            int index = FindIndex(s[len-1]);
            result += value[index];
        }//if
        return result;
    }
private:
    int FindIndex(char r){
        char roman[] = {'M','D','C','L','X','V','I'};
        for(int i = 0;i < 7;++i){
            if(r == roman[i]){
                return i;
            }//if
        }//for
        return -1;
    }
};

【分析三】

从前向后扫描,如果当前比前一个大,说明这一段的值为当前值减去上一个值(如IV = 5 -1 = 4),否则将当前值加入结果中。

有一点需要说明一下:

假如遍历到CD,遍历‘C’时,‘C’的值小于'D'的值,加入结果中,遍历‘D’时,比前一个值大,结果应该是加上当前值减去上一个值,可是再遍历‘C’时,多加了一个'C'的值

因此在遍历‘D’时应再减去一个‘C’的值。即当前值减去两个上一个值,result += map(s[i]) - 2*map(s[i-1]);

【代码三】

class Solution {
public:
    int romanToInt(string s) {
        int result = 0;
        int len = s.length();
        // 转换
        for(int i = 0;i < len;++i){
            if(i > 0 && map(s[i]) > map(s[i-1])){
                result += map(s[i]) - 2*map(s[i-1]);
            }
            else{
                result += map(s[i]);
            }
        }//for
        return result;
    }
private:
    int map(char r){
        switch(r){
            case 'M':return 1000;
            case 'D':return 500;
            case 'C':return 100;
            case 'L':return 50;
            case 'X':return 10;
            case 'V':return 5;
            case 'I':return 1;
            default:return 0;
        }
    }
};


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics