13. Roman to Integer [easy] (java)

telami included in Leetcode

2018-04-07 619 words 2 minutes views

### 题目链接

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

题目原文

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

题目翻译

给定一个罗马数字，将其转成整数。输入限制在1到3999之间。

思路方法

做题的第一步要理解题。说实话，我是不清楚罗马数字的记法的，所以查了一下资料，这里也简单介绍一下吧。

罗马数字采用七个罗马字母作数字： I（1）、X（10）、C（100）、M（1000）、V（5）、L（50）、D（500）。

记数的方法： 1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如 III=3； 2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 VIII=8、XIII=12； 3. 小的数字（限于 I、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 IV=4、IX=9； 4. 在一个数的上面画一条横线，表示这个数增值 1,000 倍。

常用数字记法举例：

Roman	Integer	Roman	Integer
I	1	XXIX	29
II	2	XXX	30
III	3	XL	40
IV	4	L	50
V	5	LX	60
VI	6	LXX	70
VII	7	LXXX	80
VIII	8	XC	90
IX	9	XCIX	99
X	10	C	100
XI	11	CI	101
XII	12	CXCIX	199
XIII	13	CC	200
XIV	14	CCC	300
XV	15	CD	400
XVI	16	D	500
XVII	17	DCLXVI	666
XVIII	18	M	1,000
XIX	19	MCMXCIX	1,999
XX	20	MM	2,000
XXI	21	MMM	3,000
XXII	22	MMMM	4,000
XXVIII	28	MMMMCMXCIX	4,999

思路一

根据上面说的计数方法的前三条。对于输入的罗马数字字符串，从后向前扫描，遇到前面数大于等于后面的最大数的时候，相加；遇到前面数小于后面的最大数的时候，相减。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public int romanToInt(String s) {
       Map<Character,Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('X',10);
        map.put('C',100);
        map.put('M',1000);
        map.put('V',5);
        map.put('L',50);
        map.put('D',500);
        int sum = 0;
        int max = 1;
        for (int i = s.toCharArray().length - 1; i >= 0 ; i--) {
            char c = s.toCharArray()[i];
            if (map.get(c) >= max){
                max = map.get(c);
                sum += map.get(c);
            }
            else{
                sum -= map.get(c);
            }
        }
        return sum;
    }
}