Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
C Solution 1:
int romanToInt(char* s) {
int res = 0;
char *p;
for (p = s; *p == 'M'; p++);
res += (p - s) * 1000;
for (s = p; *p == 'C' || *p == 'D' || *p == 'M'; p++);
if (p != s) {
if (*(p - 1) == 'M') res += 900;
else if (*(p - 1) == 'D') res += 500 - (p - s - 1) * 100;
else {
if (*s == 'C') res += (p - s) * 100;
else res += 500 + (p - s - 1) * 100;
}
}
for (s = p; *p == 'X' || *p == 'L' || *p == 'C'; p++);
if (p != s) {
if (*(p - 1) == 'C') res += 90;
else if (*(p - 1) == 'L') res += 50 - (p - s - 1) * 10;
else {
if (*s == 'X') res += (p - s) * 10;
else res += 50 + (p - s - 1) * 10;
}
}
for (s = p; *p == 'I' || *p == 'V' || *p == 'X'; p++);
if (p != s) {
if (*(p - 1) == 'X') res += 9;
else if (*(p - 1) == 'V') res += 5 - (p - s - 1);
else {
if (*s == 'I') res += p - s;
else res += 5 + (p - s - 1);
}
}
return res;
}
C Solution 2:
int romanToInt(char* s) {
int flag[256];
flag[0] = 0;
flag['I'] = 1;
flag['V'] = 5;
flag['X'] = 10;
flag['L'] = 50;
flag['C'] = 100;
flag['D'] = 500;
flag['M'] = 1000;
int res = 0;
for (; *s; s++) {
if (flag[*s] < flag[*(s + 1)]) {
res -= flag[*s];
}
else {
res += flag[*s];
}
}
return res;
}
Summary:
- The last solution clearly demonstrate the logic. For the last character, it definitely is a plus, so set
flag[0] = 0first to makeflag[*s] > flag[0]. - The first: 29ms, 34.21%. The Second: 25ms, 66.67%.
- To solve this problem, Abstracting the logic behind is the point.
LeetCode: 13. Roman to Integer





近期评论