首页 > 其他 > 详细

LeetCode Roman to Integer

时间:2014-07-21 00:15:47      阅读:292      评论:0      收藏:0      [点我收藏+]
class Solution {
private:
    const static char* pattern[];
    const static char* roman[];
    unordered_map<string, int> a2i;
public:
    int romanToInt(string s) {
        int res = 0;
        if (a2i.size() == 0) build_tlb();
        
        while (!s.empty()) {
            int len = s.length();
            for (int i=min(4, len); i>0; i--) {
                unordered_map<string, int>::iterator iter = a2i.find(s.substr(len-i));
                if (iter == a2i.end()) continue;
                res += iter->second;
                s.resize(len - i);
                break;
            }
        }
        
        return res;
    }
    
    void build_tlb() {
        int pw = 1;
        for (int i=0; i<3; i++) {
            for (int j=1; j<=9; j++) {
                string rm;
                for (int k=0; pattern[j][k] != \0; k++) {
                    rm.push_back(roman[i][ pattern[j][k] - 0 ]);
                }
                a2i.insert(make_pair(rm, pw * j));
            }
            pw *= 10;
        }
    
        a2i.insert(make_pair("M", 1000));
        a2i.insert(make_pair("MM", 2000));
        a2i.insert(make_pair("MMMM", 3000));
    }
};

const char* Solution::pattern[] = {"A", "0", "00", "000", "01", "1", "10", "100", "1000", "02"};
const char* Solution::roman[] = {"IVX", "XLC", "CDM", "M"};

580ms+,时间有点长

 

仔细观察罗马数字的话,可以把每个字母直接由一个数值替代,然后将他们累加,不过有个例外就是遇到4,9时要看字母前面一个字母的数值比如IV如果小于后面的则实际对应值为V-I = 5-1 = 4,X - I= 10 - 1 = 9

具体可以参考:http://www.cnblogs.com/zhuli19901106/p/3453180.html

LeetCode Roman to Integer,布布扣,bubuko.com

LeetCode Roman to Integer

原文:http://www.cnblogs.com/lailailai/p/3857276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!