LeetCode 13：Roman to Integer

by

2018-04-05

02:13:30

Leave a comment on LeetCode 13：Roman to Integer

LeetCode

,

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

发表回复