Roman numerals are represented by seven different symbols: I
, V
, X
, L
, C
, D
and M
.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2
is written as II
in Roman numeral, just two one's added together. 12
is written as XII
, which is simply X + II
. The number 27
is written as XXVII
, which is XX + V + II
.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII
. Instead, the number four is written as IV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX
. There are six instances where subtraction is used:
I
can be placed beforeV
(5) andX
(10) to make 4 and 9.X
can be placed beforeL
(50) andC
(100) to make 40 and 90.C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4
Example 3:
Input: s = "IX"
Output: 9
Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s
contains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M')
.- It is guaranteed that
s
is a valid roman numeral in the range[1, 3999]
.
class Solution {
public:
int romanToInt(string s) {
int weight[20] = {0};
char symbol[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
int total = 0;
for(int i=0; i<s.length(); i++){
if(s[i] == 'I')
weight[i] = 1;
if(s[i] == 'V')
weight[i] = 2;
if(s[i] == 'X')
weight[i] = 3;
if(s[i] == 'L')
weight[i] = 4;
if(s[i] == 'C')
weight[i] = 5;
if(s[i] == 'D')
weight[i] = 6;
if(s[i] == 'M')
weight[i] = 7;
}
for(int i=0; i<s.length(); i++){
if(i+1 < s.length() && weight[i] < weight[i+1]){
//special case
if(s[i+1] == 'V'){
total += 4;
}
if(s[i+1] == 'X'){
total += 9;
}
if(s[i+1] == 'L'){
total += 40;
}
if(s[i+1] == 'C'){
total += 90;
}
if(s[i+1] == 'D'){
total += 400;
}
if(s[i+1] == 'M'){
total += 900;
}
i++;
}
else{
if(s[i] == 'I')
total += 1; if(s[i] == 'V')
total += 5; if(s[i] == 'X')
total += 10; if(s[i] == 'L')
total += 50; if(s[i] == 'C')
total += 100; if(s[i] == 'D')
total += 500; if(s[i] == 'M')
total += 1000;
}
}
return total;
}
};
TIPS:
weight[20]:陣列內的20是我自己設的,輸入字串長度<20。
本來設weight[7],得到下列錯誤訊息:
Line 35: Char 28: runtime error: index 7 out of bounds for type ‘int [7]’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:44:28
special case: 權重正常左邊>右邊,若右邊>左邊則為special case,如"IV"。
Success
Runtime: 4 ms, faster than 89.69% of C++ online submissions for Roman to Integer.
Memory Usage: 6 MB, less than 71.81% of C++ online submissions for Roman to Integer.