题目:
1.思路
把给定的roman字符串分割成单个字符遍历求和。
如果当前数字比下一个大,那么sum当前值;
如果当前数字比下一个小,那么sum后一个减当前值;
2.知识点
1⃣️对于单个字符的处理,可以使用Character类(unicode 2字节)来处理更生内存。
2⃣️new 一个初始化的map,需要实例化时指定范型,然后调用HashMap内部的put方法初始化。
3⃣️在循环中使用continue是损耗循环性能的(小list?)。
4⃣️对于基本数据类型在循环中声明或者循环外效果差不多。
5⃣️把map改为switch效率更高(小数据量,大量的话map更高,因为有JIT优化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;
}
}
Comments | NOTHING