Roman to Integer – LeetCode 13
Problem
Description
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int romanToInt(string s) {
vector<int> convert;
for(auto &si: s){
switch(si){
case 'I': convert.push_back(1); break;
case 'X': convert.push_back(10); break;
case 'C': convert.push_back(100); break;
case 'M': convert.push_back(1000); break;
case 'V': convert.push_back(5); break;
case 'L': convert.push_back(50); break;
case 'D': convert.push_back(500); break;
}
}
if(convert.size() == 1) return convert[0];
vector<int> sign(convert.size(),1);
if(convert[0] < convert[1]) sign[0] = -1;
for(int i = 1; i != convert.size() - 1; ++i){
if((convert[i] < convert[i+1]) ) sign[i] = -1;
}
int sum = 0;
for(int i = 0; i != convert.size(); ++i)
sum += sign[i] * convert[i];
return sum;
}
};
|
思路
要求将罗马数字转换成数字，难点在于在大数字的左右，小数字可能是正的也可能是负的。这个版本从头向尾解析，选择使用两个vector分别记录值和正负符号。最后加和汇总，思路同样很直接。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$82$ ms,排名$53.18\%$。
Better
思路
这个版本不变思路，选择从尾向头进行解析，这样就可以在得到符号的同时直接求和，避免了vector创建等等的时间消耗。同样的，时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$52$ ms,排名$9.85\%$。
LeetCode平台测试得到的结果时长依旧有波动。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int romanToInt(string s) {
int now, prev = 0, sum = 0;
for(int i = s.size() - 1; i >= 0; --i){
switch(s[i]){
case 'I': now = 1; break;
case 'X': now = 10; break;
case 'C': now = 100; break;
case 'M': now = 1000; break;
case 'V': now = 5; break;
case 'L': now = 50; break;
case 'D': now = 500; break;
}
if(now < prev) sum -= now;
else sum += now;
prev = now;
}
return sum;
}
};
|