友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
241. 为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104。
示例 1：
输入：expression = "2-1-1" 输出：[0,2] 解释： ((2-1)-1) = 0 (2-(1-1)) = 2
示例 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 <= expression.length <= 20 -
expression由数字和算符+、-和*组成。 -
输入表达式中的所有整数值在范围
[0, 99] -
输入表达式中的所有整数都没有前导
-或+表示符号。
思路分析
看完题目首先想的是怎么插入括号。看了题解，可以按运算符将左右分为两部分进行递归求解，再分别对左右进行计算。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-03 22:37:01
*/
public List<Integer> diffWaysToCompute(String expression) {
int length = expression.length();
List<Integer> result = new ArrayList<>();
int start = 0;
while (start < length) {
if (Character.isDigit(expression.charAt(start))) {
start++;
} else {
break;
}
}
if (start >= length) {
result.add(Integer.valueOf(expression));
return result;
}
for (int i = start; i < length; i++) {
if (Character.isDigit(expression.charAt(i))) {
continue;
}
List<Integer> left = diffWaysToCompute(expression.substring(0, i));
List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
char op = expression.charAt(i);
for (Integer l : left) {
for (Integer r : right) {
if (op == '+') {
result.add(l + r);
} else if (op == '-') {
result.add(l - r);
} else if (op == '*') {
result.add(l * r);
}
}
}
}
return result;
}