13. Roman to Integer //罗马数字转整数
- Total Accepted: 121305
- Total Submissions: 280158
- Difficulty: Easy
- Contributors: Admin
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
---------------------------------第一次觉得自己这次代码很简洁-------------------------------
时间复杂度O(n)，参照12题（见下）逆向的Top Solution，得出规律——只要处理好CD，CM，XL，XC，IV，IX这几个之后其他的按单个的累加即可。
// String M[] = {"", "M", "MM", "MMM"};
// String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
// String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
// String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
if(i+1<s.size()&&(s[i+1]=='D'||s[i+1]=='M'))代码里的i+1<s.size()部分会提升很多速率…………
//本来以为去掉会提速的，结果并没有
class Solution {
public:
int romanToInt(string s) {
int result=0;
for(int i=0;i<s.size();i++){
switch(s[i]){
case 'M':result+=1000;break;
case 'D':result+=500;break;
case 'C':if(i+1<s.size()&&(s[i+1]=='D'||s[i+1]=='M'))result-=100;else result+=100;break;
case 'L':result+=50;break;
case 'X':if(i+1<s.size()&&(s[i+1]=='L'||s[i+1]=='C'))result-=10;else result+=10;break;
case 'V':result+=5;break;
case 'I':if(i+1<s.size()&&(s[i+1]=='V'||s[i+1]=='X'))result-=1;else result+=1;break;
}
}
return result;
}
};
运行结果：
难得一次击败了80%+的人，mark一下
祝刷题愉快~
