class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
}
};
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 <= 20expression 由数字和算符 '+'、'-' 和 '*' 组成。[0, 99] 原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-15 13:24:43
ADDITION = -1
SUBTRACTION = -2
MULTIPLICATION = -3
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
ops = []
i, n = 0, len(expression)
while i < n:
if expression[i].isdigit():
x = 0
while i < n and expression[i].isdigit():
x = x * 10 + int(expression[i])
i += 1
ops.append(x)
else:
if expression[i] == '+':
ops.append(ADDITION)
elif expression[i] == '-':
ops.append(SUBTRACTION)
else:
ops.append(MULTIPLICATION)
i += 1
n = len(ops)
dp = [[[] for _ in range(n)] for _ in range(n)]
for i, x in enumerate(ops):
dp[i][i] = [x]
for sz in range(3, n + 1):
for r in range(sz - 1, n, 2):
l = r - sz + 1
for k in range(l + 1, r, 2):
for x in dp[l][k - 1]:
for y in dp[k + 1][r]:
if ops[k] == ADDITION:
dp[l][r].append(x + y)
elif ops[k] == SUBTRACTION:
dp[l][r].append(x - y)
else:
dp[l][r].append(x * y)
return dp[0][-1]
python3 解法, 执行用时: 36 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-15 13:23:38
ADDITION = -1
SUBTRACTION = -2
MULTIPLICATION = -3
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
ops = []
i, n = 0, len(expression)
while i < n:
if expression[i].isdigit():
x = 0
while i < n and expression[i].isdigit():
x = x * 10 + int(expression[i])
i += 1
ops.append(x)
else:
if expression[i] == '+':
ops.append(ADDITION)
elif expression[i] == '-':
ops.append(SUBTRACTION)
else:
ops.append(MULTIPLICATION)
i += 1
@cache
def dfs(l: int, r: int) -> List[int]:
if l == r:
return [ops[l]]
res = []
for i in range(l, r, 2):
left = dfs(l, i)
right = dfs(i + 2, r)
for x in left:
for y in right:
if ops[i + 1] == ADDITION:
res.append(x + y)
elif ops[i + 1] == SUBTRACTION:
res.append(x - y)
else:
res.append(x * y)
return res
return dfs(0, len(ops) - 1)
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2022-11-15 13:21:49
import (
"fmt"
"strconv"
)
func diffWaysToCompute(input string) []int {
// 如果是数字，直接返回
if isDigit(input) {
tmp, _ := strconv.Atoi(input)
return []int{tmp}
}
// 空切片
var res []int
// 遍历字符串
for index, c := range input {
tmpC := string(c)
if tmpC == "+" || tmpC == "-" || tmpC == "*" {
// 如果是运算符，则计算左右两边的算式
left := diffWaysToCompute(input[:index])
right := diffWaysToCompute(input[index+1:])
for _, leftNum := range left {
for _, rightNum := range right {
var addNum int
if tmpC == "+" {
addNum = leftNum + rightNum
} else if tmpC == "-" {
addNum = leftNum - rightNum
} else {
addNum = leftNum * rightNum
}
res = append(res, addNum)
}
}
}
}
return res
}
// 判断是否为全数字
func isDigit(input string) bool {
_, err := strconv.Atoi(input)
if err != nil {
return false
}
return true
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-15 13:21:23
'''
该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解。
分解：按运算符分成左右两部分，分别求解
解决：实现一个递归函数，输入算式，返回算式解
合并：根据运算符合并左右两部分的解，得出最终解
'''
class Solution:
def diffWaysToCompute(self, input: str) -> List[int]:
# 如果只有数字，直接返回
if input.isdigit():
return [int(input)]
res = []
for i, char in enumerate(input):
if char in ['+', '-', '*']:
# 1.分解：遇到运算符，计算左右两侧的结果集
# 2.解决：diffWaysToCompute 递归函数求出子问题的解
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
# 3.合并：根据运算符合并子问题的解
for l in left:
for r in right:
if char == '+':
res.append(l + r)
elif char == '-':
res.append(l - r)
else:
res.append(l * r)
return res