Leetcode RomanTo Integer


题目:

Roman to Integer - LeetCode

1.思路

把给定的roman字符串分割成单个字符遍历求和。

如果当前数字比下一个大,那么sum当前值;

如果当前数字比下一个小,那么sum后一个减当前值;

2.知识点

1⃣️对于单个字符的处理,可以使用Character类(unicode 2字节)来处理更生内存。

2⃣️new 一个初始化的map,需要实例化时指定范型,然后调用HashMap内部的put方法初始化。

3⃣️在循环中使用continue是损耗循环性能的(小list?)。

4⃣️对于基本数据类型在循环中声明或者循环外效果差不多。

5⃣️把map改为switch效率更高(小数据量,大量的话map更高,因为有JIT优化map)。

Java性能测试的困惑:switch和map的性能比较

3.代码如下:

package com.eironn.leetcode;

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

public class RomanToInteger {

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

4.第二种思路

逆序整个字符串,从右向左,加上每个字符串(如果下个字符串小于当前,加一个负),好处是可以只算加法。

class Solution {

    public int romanToInt(String s) {
        int sum = getValue(s.charAt(s.length()-1));

        for(int i = s.length() - 2; i >= 0; --i) {
            int cVal = getValue(s.charAt(i));
            int pVal = getValue(s.charAt(i+1));
            sum += cVal >= pVal ? cVal : cVal*(-1);
        }

        return sum;
    }

    public int getValue(char c) {
        switch (c) {
            case 'M':
                return 1000;
            case 'D':
                return 500;
            case 'C':
                return 100;
            case 'L':
                return 50;
            case 'X' :
                return 10;
            case 'V':
                return 5;
            case 'I':
                return 1;
        }
        return 0;
    }
}

5.另一种思路

先替换特殊字符(4,9,40,90),再替换普通字符(1,5,10,50)

比较慢

public class SolutionMe4 {

    /**
     * 29 ms
     * 先替换特殊的4,9,40,90,再替换普通的。
     *
     * @param roman
     * @return
     */
    public int romanToInt(String roman) {
        int resp = 0;
        Map<String, Integer> map = new LinkedHashMap<String, Integer>() {
            {
                put("IV", 4);
                put("CM", 900);
                put("XL", 40);
                put("XC", 90);
                put("CD", 400);
                put("IX", 9);
                put("I", 1);
                put("V", 5);
                put("X", 10);
                put("L", 50);
                put("C", 100);
                put("D", 500);
                put("M", 1000);
            }
        };
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            while (roman.contains(key)) {
                resp += value;
                roman = roman.replaceFirst(key, "");
            }
        }
        return resp;
    }
}

声明:Eironn's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Leetcode RomanTo Integer


Java开发,同时会一些旁门左道。