题目描述

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

给你一个由数字和运算符组成的字符串 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] 

题解——分治+记搜

图片

思路

分治

对于一个算式来说,总是可以根据运算符分为两部分,接着分别计算结果并合并
每一个结果都是一个数组,包含这个算式的所有可能结果,计算时将左右两部分排列组合
递归的终点是字符串是纯数字,直接返回
比如示例中的2*3-4*5,有下面的分法

  • 分为2与3-4*5,对于3-4*5,继续细分
    • 3-4*5可以分为3与4*5,或者3-4与5,所以结果为{-17,-5}
    • 则这种分法产生的最终结果就是{-34,-10}
  • 分为2*3与4*5,这种分法产生的结果就是{-14}
  • 分为2*3-4与5,对于2-3*4,继续细分
    • 2*3-4可以分为2与3-4,或者2*3与4,所以结果为{-2,2}
    • 则这种分法产生的最终结果就是{-10,10}

最终结果是它们的结合,也就是{-34,-10,-14,-10,10},本题是不需要我们去重的
不论是多复杂的算式,总是可以不断分而治之,递归得到各个部分的解

记搜

由于数据量比较小,这道题不用记搜也能过,大概在4ms左右,用了记搜能提升到0ms
还是考虑上面的例子,在第一种分法里,我们已经计算过了4*5,但是在第二种分法里,我们又算了一遍
为了减少重复计算,用哈希表作备忘录,保存算式到结果的映射,每次计算时查表/存表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map<string,vector<int>> memo; 
    vector<int> diffWaysToCompute(string s) {
        if(memo.find(s)!=memo.end())//之前计算过这个算式了,直接返回
            return memo[s];
        if(s.find_first_of("+-*")==s.npos)//字符串是纯数字,直接转化返回
            return {stoi(s)};
        vector<int> ans;
        int pos=0;
        while((pos=s.find_first_of("+-*",pos+1))!=s.npos)//找到所有运算符并分左右进行计算
        {
            vector<int> left=diffWaysToCompute(s.substr(0,pos)),right=diffWaysToCompute(s.substr(pos+1));
            for(int l:left)//左右两侧结果排列组合
                for(int r:right)
                    ans.push_back(s[pos]=='+'?l+r:s[pos]=='-'?l-r:l*r);//根据运算符存结果
        }
        memo[s]=ans;//存备忘录
        return memo[s];//返回结果
    }
};