exp经验网题目 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
示例 1:
输入: “III”
输出: 3
示例 2:
输入: “IV”
输出: 4
示例 3:
输入: “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
我的思路
- 罗马数字字符串转为数组
- 从左到右进位计算 ( 遇到L X C向前探一位 )
- 获取对应值后叠加得到结果
我的Java代码 1
// 执行用时 : 19 ms , 在所有 java 提交中击败了 16.67% 的用户
// 内存消耗 : 36.9 MB , 在所有 java 提交中击败了 94.76% 的用户
public static int romanToInt(String s) {
int a = 0;
int length = s.length();
String[] arr = s.split("");
for (int j = 0; j < length; j++) {
switch (arr[j]){
case "I":
if (length <= j+1) {
a += 1;
break;
} else
if ("V".equals(arr[j+1])) {
a += 4;
j++;
} else if ("X".equals(arr[j+1])) {
a += 9;
j++;
} else {
a += 1;
}
break;
case "V":
a += 5;
break;
case "X":
if (length <= j+1) {
a += 10;
break;
} else
if ("L".equals(arr[j+1])) {
a += 40;
j++;
} else if ("C".equals(arr[j+1])) {
a += 90;
j++;
} else {
a += 10;
}
break;
case "L":
a += 50;
break;
case "C":
if (length <= j+1) {
a += 100;
break;
} else
if ("D".equals(arr[j+1])) {
a+=400;
j++;
} else if ("M".equals(arr[j+1])) {
a += 900;
j++;
} else {
a += 100;
}
break;
case "D":
a += 500;
break;
case "M":
a += 1000;
break;
default:
}
}
return a;
}大神的Java代码
// 耗时3ms
public int romanToInt(String s) {
char[] chars = s.toCharArray();
int ret = 0;
for (int i = 0, length = chars.length; i < length; i++) {
char c = chars[i];
switch (c) {
case 'M':
ret += 1000;
break;
case 'D':
ret += 500;
break;
case 'C':
if (i < length - 1) {
if (chars[i + 1] == 'M') {
ret += 900;
i++;
break;
} else if (chars[i + 1] == 'D') {
ret += 400;
i++;
break;
}
}
ret += 100;
break;
case 'L':
ret += 50;
break;
case 'X':
if (i < length - 1) {
if (chars[i + 1] == 'C') {
ret += 90;
i++;
break;
} else if (chars[i + 1] == 'L') {
ret += 40;
i++;
break;
}
}
ret += 10;
break;
case 'V':
ret += 5;
break;
default:
// I
if (i < length - 1) {
if (chars[i + 1] == 'X') {
ret += 9;
i++;
break;
} else if (chars[i + 1] == 'V') {
ret += 4;
i++;
break;
}
}
ret += 1;
break;
}
}
return ret;
}我的总结
- 基础不太好 像单个字符比较应该用String.toCharArray() 而不是直接String.split()
- 频繁的数组取值
- 字符串的比较比char比较想等耗时
调整后的代码
// 执行用时 : 4 ms , 在所有 java 提交中击败了 99.96% 的用户
// 内存消耗 : 36.6 MB , 在所有 java 提交中击败了 95.93% 的用户
public static int romanToInt(String s) {
int res = 0;
char[] chars = s.toCharArray();
for (int j = 0, length = chars.length; j < length; j++) {
char c = chars[j];
switch (c){
case 'I':
if (length <= j+1) {
res += 1;
break;
} else
if ('V' == chars[j+1]) {
res += 4;
j++;
} else if ('X' == chars[j+1]) {
res += 9;
j++;
} else {
res += 1;
}
break;
case 'V':
res += 5;
break;
case 'X':
if (length <= j+1) {
res += 10;
break;
} else
if ('L' == chars[j+1] ) {
res += 40;
j++;
} else if ('C' == chars[j+1]) {
res += 90;
j++;
} else {
res += 10;
}
break;
case 'L':
res += 50;
break;
case 'C':
if (length <= j+1) {
res += 100;
break;
} else
if ('D' == chars[j+1]) {
res+=400;
j++;
} else if ('M' == chars[j+1]) {
res += 900;
j++;
} else {
res += 100;
}
break;
case 'D':
res += 500;
break;
case 'M':
res += 1000;
break;
default:
}
}
return res;
}python 解法
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
ans=0
for i in range(len(s)):
if i<len(s)-1 and a[s[i]]<a[s[i+1]]:
ans-=a[s[i]]
else:
ans+=a[s[i]]
return ansC解法
#define nI 1 //直接用define I 1，好像会有歧义
#define nV 5
#define nX 10
#define nL 50
#define nC 100
#define nD 500
#define nM 1000
int romanToInt(char* s)
{
int num = 0, flag = 0; /*立一个flag，是因为之前我在后面会用三个if，一个else，其实我的初衷是三个if有其中任何一个满足都不要再执行else了
但是如果没有flag的话，意思是第三个if如果不成立便会跳去else，比如IV，第一个if满足，然后第三个if不满足，else这时候
就会出来执行，很不爽*/
while(*s != NULL)
{
if(*s == 'I' && (*(s + 1) == 'V' || *(s + 1) == 'X')) //接下来的这三个if都有特殊含义，所以flag=1，普通情况属于flag=0
{
flag = 1;
switch(*(s + 1))
{
case 'V':num += (nV - nI); s+=2; break;
case 'X':num += (nX - nI); s+=2; break;
}
}
if(*s == 'X' && (*(s + 1) == 'L' || *(s + 1) == 'C'))
{
flag = 1;
switch(*(s + 1))
{
case 'L':num += (nL - nX); s+=2; break;
case 'C':num += (nC - nX); s+=2; break;
}
}
if(*s == 'C' && (*(s + 1) == 'D' || *(s + 1) == 'M'))
{
flag = 1;
switch(*(s + 1))
{
case 'D':num += (nD - nC); s+=2; break;
case 'M':num += (nM - nC); s+=2; break;
}
}
if(flag == 0) //本来这里是else的，改为if(flag == 0)
{
switch(*s)
{
case 'I':num += nI; s += 1; break;
case 'V':num += nV; s += 1; break;
case 'X':num += nX; s += 1; break;
case 'L':num += nL; s += 1; break;
case 'C':num += nC; s += 1; break;
case 'D':num += nD; s += 1; break;
case 'M':num += nM; s += 1; break;
}
}
flag = 0; //最后置回普通状态
}
return num;
}