罗马数字转整数
题目描述
罗马数字包含以下七种字符: I， V， X， L，C，D 和 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 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
思路
① 确定罗马数字由哪几个英文字母组成
② 需要处理特殊的6种情况, 即左边的数字比右边的数字小时, 这两个数字需要做减法而不是加法, 否则只需要将罗马数字转换为整数再加起来即可
③编程实现
编程(JAVA为例)
-
首先给出一个我脑回路有问题的代码答案, 在leetcode上跑通了, 但是性能非常低, 枯了
性能评价1.png
class Solution {
public int romanToInt(String s) {
int sum = 0;
//拆分成一个个独立的罗马数字
String[] split = s.split("");
//判断数字是否为特殊的六种情况
if (s.length()==2){
switch (split[0]){
case "I" :
if(split[1].equals("V")){
return 4;
}else if(split[1].equals("X")){
return 9;
}else{
return 2;
}
case "X" :
if(split[1].equals("L")){
return 40;
}else if(split[1].equals("C")){
return 90;
}else if(split[1].equals("V")){
return 15;
}else if(split[1].equals("I")){
return 11;
}else if(split[1].equals("X")){
return 20;
}
case "C" :
if(split[1].equals("D")){
return 400;
}else if(split[1].equals("M")){
return 900;
}else if(split[1].equals("L")){
return 150;
}else if(split[1].equals("X")){
return 110;
}else if(split[1].equals("V")){
return 105;
}else if(split[1].equals("I")){
return 101;
}else if(split[1].equals("C")){
return 200;
}
default:
break;
}
}
//将每一个罗马数字映射在一个整型数组中
int[] nums = new int[s.length()];
for(int i = 0; i<=split.length-1; i++){
switch (split[i]) {
case "I" :
nums[i] = 1;
continue;
case "V" :
nums[i] = 5;
continue;
case "X" :
nums[i] = 10;
continue;
case "L" :
nums[i] = 50;
continue;
case "C" :
nums[i] = 100;
continue;
case "D" :
nums[i] = 500;
continue;
case "M" :
nums[i] = 1000;
continue;
default:
break;
}
}
for(int i=0;i<nums.length;i++){
if(i==nums.length-1){
sum += nums[i];
break;
}
//左边的数字比右边的数字小
if (nums[i] < nums[i+1]){
//右边的数字减去左边的数字再累加
sum += (nums[i+1] - nums[i]);
//因为右边的数字已经被使用了, 所以下标必须往右移动两位, 以免右边的数字被重复使用两遍
i++;
}else{
sum += nums[i];
System.out.println(sum);
}
}
return sum;
}
}
后来发现, 上面的特殊的6种情况的判断处理完全就是一个泥潭, 一点用处都没用, 删掉后性能跑的更快了, 虽然不是最好的
public class Solution {
public static int romanToInt(String s){
int sum = 0;
//将每一个罗马数字映射在一个整型数组中
String[] split = s.split("");
int[] nums = new int[s.length()];
for(int i = 0; i<=split.length-1; i++){
switch (split[i]) {
case "I" : nums[i] = 1;
continue;
case "V" : nums[i] = 5;
continue;
case "X" : nums[i] = 10;
continue;
case "L" : nums[i] = 50;
continue;
case "C" : nums[i] = 100;
continue;
case "D" : nums[i] = 500;
continue;
case "M" : nums[i] = 1000;
continue;
default:
break;
}
}
for(int i=0;i<nums.length;i++){
if(i==nums.length-1){
sum += nums[i];
break;
}
//左边的数字比右边的数字小
if (nums[i] < nums[i+1]){
//右边的数字减去左边的数字再累加
sum += (nums[i+1] - nums[i]);
//因为右边的数字已经被使用了, 所以下标必须往右移动两位, 以免右边的数字被重复使用两遍
i++;
}else{
sum += nums[i];
}
}
return sum;
}
}
性能评价:
性能评价2.png
总结
说实话, 其实这道题做的时候觉得很简单, 用了很多的if{...}else{...},挺恶心的, 然后绕了不少的弯路, 最后优化成这个样子也算是过关了吧, 今天就这么多吧, 代码我都懂, 重要的是思想!
