leetcode 241. 为运算表达式设计优先级
题目：241. 为运算表达式设计优先级
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例1:
输入: “2-1-1”
输出: [0, 2]
解释:
- ((2-1)-1) = 0
- (2-(1-1)) = 2
示例2:
输入: “23-45”
输出: [-34, -14, -10, -10, 10]
解释:
- (2*(3-(4*5))) = -34
- ((23)-(45)) = -14
- ((2*(3-4))*5) = -10
- (2*((3-4)*5)) = -10
- (((2*3)-4)*5) = 10
方法：分治
思路：通过分治的思想，将字符串以运算符为标识把字符串分为两个部分，然后分别计算这两个部分的值，可以继续细分的继续按运算符细分求结果，两部分中每个部分都有可能会有不同的结果（可以继续细分就会有不同的结果），所以求结果时，要将两部分不同结果组合起来，才能得出最终的结果。
运行数据：执行用时：2 ms，内存消耗：40.1 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public List<Integer> diffWaysToCompute(String input) {
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < input.length(); i++) {
char cha = input.charAt(i);
if (cha == '+' || cha == '-' || cha == '*') {
List<Integer> leftList = diffWaysToCompute(input.substring(0, i));
List<Integer> rightList = diffWaysToCompute(input.substring(i + 1));
for (Integer l : leftList) {
for (Integer r : rightList) {
switch (cha) {
case '+':
result.add(l + r);
break;
case '-':
result.add(l - r);
break;
case '*':
result.add(l * r);
break;
}
}
}
}
}
if (result.size() == 0){
result.add(Integer.valueOf(input));
}
return result;
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
