0241. 为运算表达式设计优先级

0241. 为运算表达式设计优先级 #

  • 标签:递归、记忆化搜索、数学、字符串、动态规划
  • 难度:中等

题目大意 #

描述:给定一个由数字和运算符组成的字符串 expression

要求:按不同优先级组合数字和运算符,计算并返回所有可能组合的结果。你可以按任意顺序返回答案。

说明

  • 生成的测试用例满足其对应输出值符合 $32$ 位整数范围,不同结果的数量不超过 $10^4$。
  • $1 \le expression.length \le 20$。
  • expression 由数字和算符 '+''-''*' 组成。
  • 输入表达式中的所有整数值在范围 $[0, 99]$。

示例

  • 示例 1:
1
2
3
4
5
输入expression = "2-1-1"
输出[0,2]
解释
((2-1)-1) = 0 
(2-(1-1)) = 2
  • 示例 2:
1
2
3
4
5
6
7
8
输入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 只包含有数字和字符,可以写成类似 x op y 的形式,其中 $x$、$y$ 为表达式或数字,$op$ 为字符。

则我们可以根据字符的位置,将其递归分解为 $x$、$y$ 两个部分,接着分别计算 $x$ 部分的结果与 $y$ 部分的结果。然后再将其合并。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        res = []
        if len(expression) <= 2:
            res.append(int(expression))
            return res
        
        for i in range(len(expression)):
            ch = expression[i]
            if ch == '+' or ch == '-' or ch == '*':
                left_cnts = self.diffWaysToCompute(expression[ :i])
                right_cnts = self.diffWaysToCompute(expression[i + 1:])

                for left in left_cnts:
                    for right in right_cnts:
                        if ch == '+':
                            res.append(left + right)
                        elif ch == '-':
                            res.append(left - right)
                        else:
                            res.append(left * right)
        
        return res

思路 1:复杂度分析 #

  • 时间复杂度:$O(C_n)$,其中 $n$ 为结果数组的大小,$C_n$ 是第 $k$ 个卡特兰数。
  • 空间复杂度:$O(C_n)$。
本站总访问量  次  |  您是本站第  位访问者