LeetCode 13:Roman to Integer

Given a roman numeral, convert it to an integer.

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

这里需要从罗马数字换成整型

看看记数规则

记数方法

基本字符
I
V
X
L
C
D
M
相应的阿拉伯数字表示为
1
5
10
50
100
500
1000

 

  1. 相同的数字连写、所表示的数等于这些数字相加得到的数、如:Ⅲ=3;
  2. 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如:Ⅷ=8、Ⅻ=12;
  3. 小的数字(限于 I、X 和 C)在大的数字的左边、所表示的数等于大数减小数得到的数、如:Ⅳ=4、Ⅸ=9;
  4. 正常使用时、连写的数字重复不得超过三次;
  5. 在一个数的上面画一条横线、表示这个数扩大 1000 倍。

一开始感觉挺复杂的,比如I和V,谁前谁后都行,只不过表示一个数字的时候,罗马数字小的放前面只能一次,放后面能1~3次;但是能出现组合的大的罗马字符只有V,L和D,而显然VLD在一个罗马数字里只能说现一次,但是IXC却有可能出现在相邻数字里,一个是被减,一个是减,比如XCIX=99

思路还是不太清晰,列举一些找找规律,参考了下Solution

/**
* 罗马字符 I V X L C D M
* 整数数字 1 5 10 50 100 500 1000
* MMMCMXCIX = 3999
* MCM = 1900 = M + C + C + M - C = M + C + M - 2 * C
* MCMXCVI = 1996 = M + M - C + C - X + V + I
* = M + C + M - 2 * C + X + C - 2 * X + V + I
* CMX = 910 = C + M - 2 * C + X
* VIII = 8 = V + I + I + I
* @param s
* @return intNum
*/

如果next比当前小,直接加next即可,就算VIII,5+1+1+1

如果next和当前相等,直接加next即可,比如III,1+1+1

如果next比当前self大,(sum – self) + next – self = sum + next – 2 * self

Java源码如下

package com.maoxiaomeng;

import java.util.HashMap;
import java.util.Map;

/**
* @author lihui
* @date 2018/4/05 01:11
*/

public class Solution {
/**
* 罗马字符 I V X L C D M
* 整数数字 1 5 10 50 100 500 1000
* MMMCMXCIX = 3999
* MCM = 1900 = M + C + C + M - C = M + C + M - 2 * C
* MCMXCVI = 1996 = M + M - C + C - X + V + I
* = M + C + M - 2 * C + X + C - 2 * X + V + I
* CMX = 910 = C + M - 2 * C + X
* VIII = 8 = V + I + I + I
* @param s
* @return intNum
*/
public int romanToInt(String s) {
char[] romanArray = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
int[] intArray = {1, 5, 10, 50, 100, 500, 1000};
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < romanArray.length; i++) {
map.put(romanArray[i], intArray[i]);
}

int intNum = map.get(s.charAt(0));
for (int i = 1; i < s.length(); i++) {
if (map.get(s.charAt(i)) > map.get(s.charAt(i - 1))) {
intNum = intNum + map.get(s.charAt(i)) - 2 * map.get(s.charAt(i - 1));
} else {
intNum = intNum + map.get(s.charAt(i));
}
}

return intNum;
}
}

正好电影也结束,Perfect

发表评论