LeetCode-241. 为运算表达式设计优先级-Java-medium

题目链接

法一（分治法 + 备忘录）

/**
* map存储每个字符串对应的结果
*/
private Map<String, List<Integer>> map = new HashMap<>();
/**
* 运算
*
* @param a
* @param b
* @param c
* @return
*/
private int operation(int a, int b, int c) {
if (c == '+') {
return a + b;
} else if (c == '-') {
return a - b;
} else {
return a * b;
}
}
/**
* 法一（分治法 + 备忘录）
* （1）碰到运算符号，递归求解前一半的值和后一半的值，然后根据运算符号，计算两者构成的值
* （2）因为某个字符串可能在之前已经计算过，所以可以用map存储每个字符串对应的结果，先检查map里面有没有，
*
有的话就直接返回value，没有的话才进行计算
*
* @param expression
* @return
*/
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> ans = new LinkedList<>();
if (expression.length() < 3) { // 递归结束条件，只剩下数字时，返回只包含该数的list即可
ans.add(Integer.parseInt(expression));
return ans;
}
if (map.containsKey(expression)) { // 备忘录，避免重复计算
return map.get(expression);
}
for (int i = 1; i < expression.length() - 1; i++) {
char c = expression.charAt(i);
if (c < 48 || c > 57) { // 如果第i位是符号位，根据符号位把字符串划分为左右两部分，并且分别递归获取左右list
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1, expression.length()));
for (Integer a : left) { // 分别遍历左右list，并根据当前运算符对里面的数进行运算
for (Integer b : right) {
ans.add(operation(a, b, c)); // 运算后的结果添加到新的list中
}
}
}
}
map.put(expression, ans);
return ans;
}

本地测试

/**
* 241. 为运算表达式设计优先级
*/
lay.showTitle(241);
Solution241 sol241 = new Solution241();
String expression241 = "2*3-4*5";
System.out.println(expression241);
System.out.println(sol241.diffWaysToCompute(expression241));

最后

以上就是激动灰狼为你收集整理的LeetCode-241. 为运算表达式设计优先级-Java-medium的全部内容，希望文章能够帮你解决LeetCode-241. 为运算表达式设计优先级-Java-medium所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。