RomanToInteger [source code]

public class RomanToInteger {
    public int romanToInt(String s) {
        if (s.length() == 0) return -1;
        char[] ar = s.toCharArray();
        int i = ar.length - 1;
        int res = 0;
        while (i >= 0) {
            int num = symbolToInt(ar[i]);
            if (num == 1 || i == 0) {
                res += num;
                i--;
            } else {
                int prevNum = symbolToInt(ar[i - 1]);
                if (prevNum < num) {
                    res += num - prevNum;
                    i -= 2;
                } else {
                    res += num;
                    i--;
                }
            }
        }
        return res; 
    }

    public int symbolToInt(char ch) {
        if (ch == 'M') return 1000;
        else if (ch == 'D') return 500;
        else if (ch == 'C') return 100;
        else if (ch == 'L') return 50;
        else if (ch == 'X') return 10;
        else if (ch == 'V') return 5;
        else if (ch == 'I') return 1;
        else return 0;
    }
}

感觉不是一个特别简单的题目, 能想到的办法就是从右往左扫, 然后每一步都往前 probe 一步, 看看是否需要包括前一位一起 parse.
parse 问题的话, 有时候选择好 parse 的顺序也是很重要的, 如果是普通的十进制数这种, 我们都是一般从左到右比较好 parse, 但是这个罗马数字好像我现在个人感觉是从右往左要好 parse 一点;

另外这个算法我故意大量使用 ifelse 来避免使用 break; 这样代码易读一些, 其实效果应该是等价的;

速度最后是128ms, 6%, 惨不忍睹;

这一题, 在对于"IV" 这样的数的处理上, 其实还是类似于是用逻辑来做的, 不过要意识到, 有可能以后遇到类似的题目, 更好的思路不是依赖于逻辑, 而是直接对这几个反常规的数进行枚举: rule vs. enumeration . 而且本着简单升级的思路, 枚举总是可以作为你的第一步的. 这种小局面上的逻辑, 如果一开始设计算法的时候就太纠结, 会加重做题过程中的负担和压力, 不利于相处大局上的算法;

ch.equals('M')

这个写法居然是错的, String 的话, 是必须要用 equals 来写, 但是 char 就不行. 给的提示信息是char cannot be dereferenced, 所以意思就是 equals 其实比较的就是一个equality between things pointed to的意思;

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