分治算法的基本思想是：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可以得到原问题的解
分治相关题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
|
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
42
43
44
45
|
public class Divide {
public static List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+':
ways.add(l + r);
break;
case '-':
ways.add(l - r);
break;
case '*':
ways.add(l * r);
break;
default:
break;
}
}
}
}
}
if (ways.size() == 0){
ways.add(Integer.parseInt(input));
}
return ways;
}
public static void main(String[] args) {
String input = "2*3-4*5";
List<Integer> list = diffWaysToCompute(input);
for (Integer i : list){
System.out.printf("%d ", i);
}
}
}
|
具体题目可以查看241. 为运算表达式设计优先级
