入门力扣自学笔记79 C++ （题目编号241）题目：示例 1：示例 2：提示：思路：代码：

106 阅读 0 评论 70 点赞

我是靠谱客的博主勤恳过客，这篇文章主要介绍入门力扣自学笔记79 C++ （题目编号241）题目：示例 1：示例 2：提示：思路：代码：，现在分享给大家，希望可以做个参考。

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]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

本题，将字符串的运算符作为中间节点，左侧分为一组，右侧分为一组。
递归得到，左边字符串的组合结果和右边字符串的结果。
然后将左右字符串的结果通过运算符合并起来。

代码：

复制代码

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ways;
        int len=expression.size();
        //到达边界
        if(len==1||len==2){
            ways.push_back(stoi(expression));
            return ways;
        }
        for(int i=0;i<len;i++){
            int c=expression[i];
            if(c=='+'||c=='-'||c=='*'){
                //分解得到左边字符串的组合结果
               vector<int> left_ways=diffWaysToCompute(expression.substr(0,i));
                //分解得到右边字符串的组合结果
                vector<int> right_ways=diffWaysToCompute(expression.substr(i+1));
                //将组合结果通过运算符组合
                for(auto &l:left_ways){
                    for(auto &r:right_ways){
                        switch(c){
                            case '+': ways.push_back(l+r); break;
                            case '-': ways.push_back(l-r); break;
                            case '*': ways.push_back(l*r); break;
                        }
                    }
                }
            }
        }
        //返回合并后的结果
        return ways;
    }
};

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
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ways;
        int len=expression.size();
        //到达边界
        if(len==1||len==2){
            ways.push_back(stoi(expression));
            return ways;
        }
        for(int i=0;i<len;i++){
            int c=expression[i];
            if(c=='+'||c=='-'||c=='*'){
                //分解得到左边字符串的组合结果
               vector<int> left_ways=diffWaysToCompute(expression.substr(0,i));
                //分解得到右边字符串的组合结果
                vector<int> right_ways=diffWaysToCompute(expression.substr(i+1));
                //将组合结果通过运算符组合
                for(auto &l:left_ways){
                    for(auto &r:right_ways){
                        switch(c){
                            case '+': ways.push_back(l+r); break;
                            case '-': ways.push_back(l-r); break;
                            case '*': ways.push_back(l*r); break;
                        }
                    }
                }
            }
        }
        //返回合并后的结果
        return ways;
    }
};