题目:
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:如有不正确或提高效率的方法,欢迎留言,谢谢!
原标题:No.013:Roman to Integer
关键词: