你的位置:首页 > Java教程

[Java教程]No.013:Roman to Integer


题目:

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

官方难度:

Easy

翻译:

给定一个罗马数字,翻译成一个阿拉伯数字的整数形式。输入的罗马数字范围在1-3999之间。

思路:

1. 罗马数字规则见上一章No.012。

2. 输入不考虑非罗马数字的形式,或者是错误的罗马数字形式(如IVI)。

3. 需要一个罗马字符,转译成数字的字典方法。

4. 依次读取输入字符串的对应位置的罗马数字,累加。

5. 需要考虑4和9的特殊情况。维护一个previous的int型的变量,用来记录上一个罗马字符串代表的数字,发现当前数字的值是previous的5倍或是10倍,即为4和9的情况,减回去。

解题中可能遇到的困难:

1. 出现4和9的情况,减回去的值是previous的两倍,因为之前已经累加过一次previous了。

2. previous赋初值的时候,不要影响第一次计算,因为会判断current/previous的值,可以给一个负值,或者加一个i!=0的条件,将判断从第一次循环中摒弃。

3. 在创建字典方法的时候,一般会采取switch-case-default结构,在Java7之前,switch后面的括号里的变量类型,是不能为String类型的,因此尽量采用char类型来保存罗马数字。

解题代码:

 1 // 不考虑非法的罗马字符串形式 2   private static int method(String roman) { 3     char[] array = roman.toCharArray(); 4     int sum = 0; 5     // 上一个字符串代表的值,赋初始值不要影响第一次计算 6     int previous = -1; 7     int current; 8     for (int i = 0; i < array.length; i++) { 9       current = romanDict(array[i]);10       // 特殊的4、9处理11       if (current / previous == 5 || current / previous == 10) {12         sum -= 2 * previous;13       }14       sum += current;15       previous = current;16     }17     return sum;18   }19 20   // 罗马数字转化字典21   private static int romanDict(char str) {22     switch (str) {23     case 'I':24       return 1;25     case 'V':26       return 5;27     case 'X':28       return 10;29     case 'L':30       return 50;31     case 'C':32       return 100;33     case 'D':34       return 500;35     case 'M':36       return 1000;37     default:38       return 0;39     }40   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q013.java

LeetCode题目地址:

https://leetcode.com/problems/roman-to-integer/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!