这个题目，一开始想的思路是 a ? b ? c ? d ? e ... 分解为 (a ? b) ? c ? d ? e ... 和 a ? (b ? c ? d ? e ...) 但是按照这个思路代码写不出来。看了一眼别人的代码，原来是按照每个运算符的位置，把问题分成两个子问题，然后递归求解。代码很简单，看一眼就知道怎么写的那种。但是感觉如果没有做过的话，很难一开始就想到这个方法。最后是分治+缓存解决。
class Solution {
public List<Integer> diffWaysToCompute(String input) {
return ways(input, new HashMap<>());
}
List<Integer> ways(String input, Map<String, List<Integer>> cache) {
{
List<Integer> cachedRes = cache.get(input);
if (cachedRes != null) return cachedRes;
}
List<Integer> res = new LinkedList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if ("+-*".indexOf(c) != -1) {
List<Integer> lefts = ways(input.substring(0, i), cache);
List<Integer> rights = ways(input.substring(i + 1), cache);
for (Integer left : lefts) {
for (Integer right : rights) {
if (c == '+') {
res.add(left + right);
} else if (c == '-') {
res.add(left - right);
} else if (c == '*') {
res.add(left * right);
}
}
}
}
}
if (res.isEmpty()) {
res.add(Integer.parseInt(input));
}
cache.put(input, res);
return res;
}
}
网友评论