RomanToIntegerOPT [source code]

public class RomanToIntegerOPT {
    public int romanToInt(String s) {
    int nums[] = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)) {
            case 'M':
                nums[i]=1000;
                break;
            case 'D':
                nums[i]=500;
                break;
            case 'C':
                nums[i]=100;
                break;
            case 'L':
                nums[i]=50;
                break;
            case 'X' :
                nums[i]=10;
                break;
            case 'V':
                nums[i]=5;
                break;
            case 'I':
                nums[i]=1;
                break;
        }
    }
    int sum = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] < nums[i + 1]) sum -= nums[i];
        else sum += nums[i];
    }
    return sum + nums[nums.length - 1];
    }
}

这个是 submission 最优解, 88ms, 96%;

这个人对于这个逻辑看的比我清晰, 在他看来所有的 symbol 只分为两种, 要么是用来减的, 要么是用来加的. 这个逻辑比我的简单清晰很多;

这个是 discussion 里面一个年代比较久远的解:

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;      
}

虽然这个解不算特别快, 不过这个人的想法还是挺有意思的; 这个思路应该是最直接的一个思路了, 代码写起来也简单;

我感觉我没有想出这种代码, 还是对题目本身的个性的理解不够深刻, 太沉迷于 stream 类算法的框架里面了;

这个是一个不错的解:

public static int romanToInt(String s) {  
    int res = 0;  
    for (int i = s.length() - 1; i >= 0; i--) {  
        char c = s.charAt(i);  
        switch (c) {  
        case 'I':  
            res += (res >= 5 ? -1 : 1);  
            break;  
        case 'V':  
            res += 5;  
            break;  
        case 'X':  
            res += 10 * (res >= 50 ? -1 : 1);  
            break;  
        case 'L':  
            res += 50;  
            break;  
        case 'C':  
            res += 100 * (res >= 500 ? -1 : 1);  
            break;  
        case 'D':  
            res += 500;  
            break;  
        case 'M':  
            res += 1000;  
            break;  
        }  
    }  
    return res;  
}

只用一个 pass. 他的加减法的判断利用的是从右到左扫的过程中, 当前 symbol 是否比右侧目前的 sum 要大; 这个想法比较奇特;
不过感觉他这里的排除还不够彻底, 比如"VD" 这个应该是495, 他这个算法就解不出来; 不过这个想法还是很好的;
如果要改起来好像还是很麻烦, 就完全不如这里这个最优解了;

Problem Description

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Difficulty:Easy
Category:Algorithms
Acceptance:45.20%
Contributor: LeetCode
Companies
microsoft bloomberg uber facebook yahoo
Related Topics
math string
Similar Questions
Integer to Roman