Saturday, November 22, 2014

[LeetCode] Roman to Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

思路:

Integer to Roman那题的follow up。关键还是解决例如IV = 4的subtractive notation的情况。可以用与Integer to Roman那题一样的思路扩展罗马字符到字符组合:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int romanToInt(string s) {
        string dict[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int num[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        int i=0, index=0, ret=0;
        while(i<s.size() && index<13) {
            string target = dict[index];
            string cur = s.substr(i,target.size());
            if(cur==target) {
                ret += num[index];
                i += target.size();
            }
            else {
                index++;
            }
        }
        return ret;
    }
};


更简洁清楚的解法:
找下subtractive notation的规律,以简单的例子s = IX 说明。
1. 如果按照additive性质的话应该ret = 1+10 = 11。但因为num(X)=10>num(I)=1,ret = 10 - 1。
2. 将subtractive rule转换成等效的additive rule:ret = 1 + (10 - 2*1)

建立一个罗马字符对应整数的hash table ht。
当ht[s[i]] > ht[s[i-1]],即为subtractive nontation:ret += (ht[s[i]] - 2*ht[s[i-1]])
否则为additive nontation:ret+=ht[s[i]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int romanToInt(string s) {
        if(s.empty()) return 0;
        unordered_map<char,int> ht({{'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000}});
        int ret = 0;
        for(int i=0; i<s.size(); i++) {
            if(ht.count(s[i])==0) return 0;
            ret += ht[s[i]];
            if(i!=0 && ht[s[i]]>ht[s[i-1]])
                ret -= 2*ht[s[i-1]];
        }
        return ret;
    }
};

No comments:

Post a Comment