LC241. 为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
输入：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
思路一：分治 + 记忆化递归
- 处理字符串，将数字和符号分别放到不同的数组中
- 分治：按符号进行遍历，以此符号为跟节点，两边递归去得到每边能得到的结果列表
- 用 map 存储结果链表，从而减少递归次数
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
class Solution {
HashMap<Integer, List<Integer>> map = new HashMap<>();
List<Integer> numList = new ArrayList<>();
List<Character> charList = new ArrayList<>();
int K = 100001;
public List<Integer> diffWaysToCompute(String ex) {
// 处理字符串
initList(ex);
// 递归遍历
return dfs(0, numList.size() - 1);
}
List<Integer> dfs(int l, int r) {
List<Integer> res = new ArrayList<>();
// 表示该部分只有一个数字，直接返回
if (l == r) {
res.add(numList.get(l));
return res;
}
// 如果此部分在之前已经计算过，则直接返回结果集
if (map.get(l * K + r) != null) {
return map.get(l * K + r);
}
// 遍历每个符号，以符号为分割点，分成左右两部分
for (int i = l; i < r; i++) {
List<Integer> res1 = dfs(l, i), res2 = dfs(i+1, r);
// 将得到的两个集合组合到一起
for (int n1 : res1) {
for (int n2 : res2) {
res.add(caculate(n1, charList.get(i), n2));
}
}
}
map.put(l * K + r, res);
return res;
}
// 处理字符串
void initList(String ex) {
int n = ex.length(), i = 0;
while (i < n) {
if (isOperation(ex.charAt(i))) {
charList.add(ex.charAt(i++));
} else {
int num = ex.charAt(i++) - '0';
while (i < n && !isOperation(ex.charAt(i))) {
num = num * 10 + ex.charAt(i++) - '0';
}
numList.add(num);
}
}
}
int caculate(int num1, char c, int num2) {
switch(c) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
}
return -1;
}
boolean isOperation(char c) {
return c == '+' || c == '-' || c == '*';
}
}
|
思路二：动态规划
- 处理字符串，将数字和符号分别放到不同的数组中
- 创建 dp[][] 数组，dp[i][j] 表示从第 i 个数字到第 j 个数字直接能产生的结果集
- 以长度为切入点，当只有一个数字时，dp[i][i]，一直遍历到有 n 个数字
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
class Solution {
HashMap<Integer, List<Integer>> map = new HashMap<>();
List<Integer> numList = new ArrayList<>();
List<Character> charList = new ArrayList<>();
int K = 100001;
public List<Integer> diffWaysToCompute(String ex) {
// 处理字符串
initList(ex);
int n = numList.size();
// 创建 dp
ArrayList<Integer>[][] dp = (ArrayList<Integer>[][]) new ArrayList[n][n];
// 当长度为 1 时
for (int i = 0; i < n; i++) {
ArrayList<Integer> list = new ArrayList<>();
list.add(numList.get(i));
dp[i][i] = list;
}
// 长度从 2 到 n 个数字
for (int k = 1; k < n; k++) {
// 开始下标
for (int i = 0; i < n - k; i++) {
// 结束下标
int j = i + k;
ArrayList<Integer> res = new ArrayList<>();
// 遍历分割点
for (int x = i; x < j; x++) {
ArrayList<Integer> res1 = dp[i][x], res2 = dp[x+1][j];
//System.out.println(i + " " + j + " " + x);
for (int n1 : res1) {
for (int n2 : res2) {
res.add(caculate(n1, charList.get(x), n2));
}
}
}
dp[i][j] = res;
}
}
return dp[0][n-1];
}
void initList(String ex) {
int n = ex.length(), i = 0;
while (i < n) {
if (isOperation(ex.charAt(i))) {
charList.add(ex.charAt(i++));
} else {
int num = ex.charAt(i++) - '0';
while (i < n && !isOperation(ex.charAt(i))) {
num = num * 10 + ex.charAt(i++) - '0';
}
numList.add(num);
}
}
}
int caculate(int num1, char c, int num2) {
switch(c) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
}
return -1;
}
boolean isOperation(char c) {
return c == '+' || c == '-' || c == '*';
}
}
|