241.为运算表达式设计优先级
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
示例 1：输入：expression = “2-1-1” 输出：[0,2]
解释：((2-1)-1) = 0
(2-(1-1)) = 2示例 2：输入：expression = “23-45” 输出：[-34,-14,-10,-10,10]
解释：
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
分析:
1.设计优先级就是任意加括号, 枚举各种加括号的结果
2.添加括号的方式怎么枚举?
例如对于1 + 2 3 - 4 5, 我们发现加括号其实是按照运算符号来加括号的, 我们先加一个括号
(1) + (2 3 - 4 5)
(1 + 2) + (3 - 4 5)
(1 + 2 + 3) - (4 5)
(1 + 2 + 3 - 4) * (5)
对于 (1 + 2 + 3) - (4 * 5) 这种情况的左边
1 + 2 + 3
同样可以有两种加括号的方式
(1) + (2 + 3)
(1 + 2) + (3)
3.因此对于这类问题, 我们设计一个函数可以递归地分治它, 先写一个框架
vector<int> diffWaysToCompute("(1 + 2 + 3) - (4 * 5)") {
vector<int> res;
// 分
vector<int> left = diffWaysToCompute("(1 + 2 + 3)");
vector<int> right = diffWaysToCompute("(4 * 5)");
// 治
for (int a : left) {
for (int b : right) {
res.emplace_back(a - b);
}
}
return res;
}
借助以上思路, 得到完整结果
class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
vector<int> res;
for (int i = 0; i < expression.size(); ++i) {
if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
vector<int> left = diffWaysToCompute(expression.substr(0, i));
vector<int> right = diffWaysToCompute(expression.substr(i+1));
for (auto& l : left) {
for (auto& r : right) {
if (expression[i] == '+') {
res.emplace_back(l + r);
} else if (expression[i] == '-') {
res.emplace_back(l - r);
} else if (expression[i] == '*') {
res.emplace_back(l * r);
}
}
}
}
}
// 处理单个数字的情况
if (res.empty()) {
res.emplace_back(atoi(expression.c_str()));
}
return res;
}
};
转载请注明来源, from goldandrabbit.github.io
