LeetCode13 Roman to Integer

用户1665735

发布于 2019-02-19 12:59:31

3390

发布于 2019-02-19 12:59:31

文章被收录于专栏：kevindroid

题目

Given a roman numeral, convert it to an integer.

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

解题思路

罗马数字的规则参考这个。总结起来就是如果前一位数字大于后一位，就加上其值，小于就减去其值，前提是数字长度大于一。

public int romanToInt(String s) {
        HashMap<Character, Integer> romanChar = new HashMap<>();
        int sum = 0;
        romanChar.put('I', 1);
        romanChar.put('V', 5);
        romanChar.put('X', 10);
        romanChar.put('L', 50);
        romanChar.put('C', 100);
        romanChar.put('D', 500);
        romanChar.put('M', 1000);
        if (s.length() == 1) return romanChar.get(s.charAt(0));
        for (int i = 0; i < s.length(); i++) {
            int current = romanChar.get(s.charAt(i));
            if (i < s.length() - 1 && current < romanChar.get(s.charAt(i + 1)))
                sum += (-current);
            else sum += current;
        }
        return sum;
    }

使用hashmap完成字母与值的对应关系，但是很明显耗时较长。优化一下，使用两个数组相互对应。

public int romanToInt(String s) {
        int[] val = new int[]{1,5,10,50,100,500,1000};
        int sum = 0;
        if (s.length() == 1) return val[charIndex(s.charAt(0))];
        for (int i = 0; i < s.length(); i++) {
            int current = val[charIndex(s.charAt(i))];
            if (i < s.length() - 1 && current < val[charIndex(s.charAt(i + 1))])
                sum += (-current);
            else sum += current;
        }
        return sum;
    }

    private int charIndex(char c){
        char[] key = new char[]{'I','V','X','L','C','D','M'};
        int result = 0;
        for(int i=0;i<7;i++){
            if (key[i] == c){
                result = i;
                break;
            }
        }
        return result;
    }

这样耗时少多了。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年02月19日，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap