【LeetCode】 241. 为运算表达式设计优先级

问题描述

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "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

分治

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 首先按操作符循环，即确定分治的出发点。然后分别计算操作符左边结果和操作符右边结果。

class Solution {
private:
    vector<int> dfs(const string& input, int s, int e) {
        vector<int> ans;
        for (int i = s+1; i < e; ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = dfs(input, s, i);
                vector<int> right = dfs(input, i+1, e);
                for (auto l : left) for (auto r : right) ans.push_back(ops(l, input[i], r));
            }
        }
        // 全是数字
        if (ans.size() == 0) ans.push_back(stoi(input.substr(s, e-s)));
        return ans;
    }
    int ops(int l, char op, int r) {
        switch (op) {
            case '+': return l+r;
            case '-': return l-r;
            case '*': return l*r;
            default: break;  // error!
        }
        return -1;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        return dfs(input, 0, input.size());
    }
};

明白一个函数的作用并相信它能完成这个任务，千万不要试图跳进细节

如果在使用分治思想递归过程觉得大问题和子问题函数的返回值不同，说明这个问题分解没想清楚，否则必然是相同的问题，相同的返回值类型。

带备忘录的分治

class Solution {
private:
    // 不能使用unordered_map, 因为pair没有hash函数
    map<pair<int, int>, vector<int>> res_map;
    vector<int> dfs(const string& input, int s, int e) {
        if (res_map.find(make_pair(s, e)) != res_map.end()) return res_map[make_pair(s, e)];
        vector<int> ans;
        for (int i = s+1; i < e; ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = dfs(input, s, i);
                vector<int> right = dfs(input, i+1, e);
                for (auto l : left) for (auto r : right) ans.push_back(ops(l, input[i], r));
            }
        }
        // 全是数字
        if (ans.size() == 0) ans.push_back(stoi(input.substr(s, e-s)));
        // res_map.insert(make_pair(make_pair(s, e), ans));
        res_map[make_pair(s, e)] = ans;  // 高效一些
        return ans;
    }
    int ops(int l, char op, int r) {
        switch (op) {
            case '+': return l+r;
            case '-': return l-r;
            case '*': return l*r;
            default: break;  // error!
        }
        return -1;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        return dfs(input, 0, input.size());
    }
};