LeetCode241 为运算表达式设计优先级

发表于 | 分类于 |
字数统计: 583 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/

题面

给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果。

解法

利用分治思想，将加括号转化为，对于每个运算符号，先执行处理两侧的表达式，在进行符号的计算。
比如对于 2 * 3 - 4 * 5 对于第一个乘号，处理完左边的2和右边的3 - 4 * 5后把结果进行相乘
用递归的方式可以很好的处理这一问题
其实当时也有点感觉 但是没写出来
是一道很好的题目

分治写法后发现某个字符串可能被计算了很多次，因此可以使用记忆化的方法进行优化
分治+记忆化又可以写成动态规划
设计状态dp[i][j]表示第i个数字到第j个数字能组成的所有结果
dp[i][j]可以从中间的每一个运算符两端的表达式dp[i][k]和dp[k + 1][j]转移而来
细节见代码

代码

分治做法

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
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        int len = expression.size();
        for (int i = 0; i < len; i++) {
            char c = expression[i];
            if (isdigit(c) == 0) {
                auto left = diffWaysToCompute(expression.substr(0, i));
                auto right = diffWaysToCompute(expression.substr(i + 1));
                for(int l: left) {
                    for (int r: right) {
                        switch (c)
                        {
                        case '+'/* constant-expression */:
                            res.push_back(l + r);
                            break;
                        case '-':
                            res.push_back(l - r);
                            break;
                        case '*':
                            res.push_back(l * r);
                            break;
                        default:
                            break;
                        }
                    }
                }
            }
        }
        if (res.empty()) {
            res.push_back(stoi(expression));
        }
        return res;

    }
};

dp做法

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
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        
        int num = 0;
        char op;
        istringstream is(expression + "+");
        vector<int> numbers;
        vector<char> ops;
        while(is >> num && is >> op) {
            numbers.push_back(num);
            ops.push_back(op);
        }
        int siz = numbers.size();
        vector<vector<vector<int>>> dp(siz, vector<vector<int>>(siz, vector<int>()));
        for (int i = 0; i < siz; i++) {
            for (int j = i; j >= 0; j--) {
            if (i == j) {
                dp[i][i].push_back(numbers[i]);
            }
            else {
                for (int k = j; k < i; k++) {
                    auto left = dp[j][k];
                    auto right = dp[k + 1][i];
                    for(int l: left) {
                        for (int r: right) {
                            switch (ops[k])
                            {
                            case '+':
                                dp[j][i].push_back(l + r);
                                break;
                            case '-':
                                dp[j][i].push_back(l - r);
                                break;
                            case '*':
                                dp[j][i].push_back(l * r);
                                break;
                            default:
                                break;
                            }
                        }
                    }
                }
            }
            }

        }
        return dp[0][siz - 1];

    }
};