leetcode Daily Challenge on Feburary 20th, 2021.
Difficulty : Easy
Related Topics : Math、String
Roman numerals are represented by seven different symbols:
I
,V
,X
,L
,C
,D
andM
.Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example, two is written as
II
in Roman numeral, just two one's added together. Twelve is written as,XII
, which is simplyX
+II
. The number twenty seven is written asXXVII
, which isXX
+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 asIV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written asIX
. 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. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: "III" Output: 3
Input: "IV" Output: 4
Input: "IX" Output: 9
Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
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]
.
- mine
- Java
Runtime: 6 ms, faster than 51.46%, Memory Usage: 36.7 MB, less than 100.00% of Java online submissions
// O(N)time // O(N)space public int romanToInt(String s) { List<Character> list = new ArrayList<>(); list.add('I'); list.add('V'); list.add('X'); list.add('L'); list.add('C'); list.add('D'); list.add('M'); List<Integer> cache = new ArrayList<>(); cache.add(1); cache.add(5); cache.add(10); cache.add(50); cache.add(100); cache.add(500); cache.add(1000); int res = 0; char[] chars = s.toCharArray(); int index = 0; while (index + 1 < chars.length) { int f = list.indexOf(chars[index]); int n = list.indexOf(chars[index + 1]); if (f < n) { //IV、VX... res += cache.get(n) - cache.get(f); index += 2; } else { res += cache.get(f); index++; } } if (index + 1 == chars.length) { res += cache.get(list.indexOf(chars[index])); } return res; }
- Java
- the most votes
Runtime: 4 ms, faster than 73.02%, Memory Usage: 36 MB, less than 100.00% of Java online submissions
// O(N)time // O(N)space public int romanToInt(String s) { int sum=0; if(s.indexOf("IV")!=-1){sum-=2;} if(s.indexOf("IX")!=-1){sum-=2;} if(s.indexOf("XL")!=-1){sum-=20;} if(s.indexOf("XC")!=-1){sum-=20;} if(s.indexOf("CD")!=-1){sum-=200;} if(s.indexOf("CM")!=-1){sum-=200;} char c[]=s.toCharArray(); int count=0; for(;count<=s.length()-1;count++){ if(c[count]=='M') sum+=1000; if(c[count]=='D') sum+=500; if(c[count]=='C') sum+=100; if(c[count]=='L') sum+=50; if(c[count]=='X') sum+=10; if(c[count]=='V') sum+=5; if(c[count]=='I') sum+=1; } return sum; }