算法题: 罗马数字转整数 内附多种解法及思路 LeetCode 第13题

题目 罗马数字转整数

罗马数字包含以下七种字符: I, V, X, LCD 和 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 ans

C解法

#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;
}
赞(1) 打赏
未经允许不得转载:exp经验网 » 算法题: 罗马数字转整数 内附多种解法及思路
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

寻找有兴趣的小伙伴, 加入我们吧!

加入我们