深圳建设招标网站首页,标准百度网站建设,网上商城系统论文,商业网站的规划和设计241. 为运算表达式设计优先级#xff08;中等#xff09; 解法一#xff1a;分治法
对于这道题#xff0c;加括号其实就是决定运算次序#xff0c;所以我们可以把加括号转化为#xff0c;「对于每个运算符号#xff0c;先执行处理两侧的数学表达式#xff0c;再处理此…241. 为运算表达式设计优先级中等 解法一分治法
对于这道题加括号其实就是决定运算次序所以我们可以把加括号转化为「对于每个运算符号先执行处理两侧的数学表达式再处理此运算符号」。
对于一个形如 x op y 的算式而言它的结果组合取决于 x 和 y 的结果组合数 而 x 和 y 又可以写成形如 x op y 的算式。
因此该问题的子问题就是 x op y 中的 x 和 y以运算符分隔的左右两侧算式解 。
对于分治算法分成三步走
分解按照运算符分隔成左右两部分分别求解解决通过递归实现最终我们会得到只包含数字的算式返回数字作为算式解合并根据运算符合并左右两部分的解得出最终解。
代码
class Solution {
public:vectorint diffWaysToCompute(string expression) {vectorint ans, left, right;int flag 0; int n expression.size();for(int i0; in; i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag 1; // flag1说明string是表达式flag0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left diffWaysToCompute(string(expression, 0, i));right diffWaysToCompute(string(expression, i1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] ) ans.push_back(l r);if(expression[i] -) ans.push_back(l - r);if(expression[i] *) ans.push_back(l * r);}}}}if(flag 0){// expression 只是一个数字// {int} - vectorintreturn {stoi(expression)};}return ans;}
};解法二分治法记忆化
解法一中存在重复运算比如 2*3 - 4*5 按照第一个 * 分割右边部分是 3 - 4*5 进而计算 4*5 而按照 - 分割同样会再次计算 4*5 。
为了减少重复运算可以使用记忆化搜索保存字符串区间[l,r]的运算结果整个思路和解法一类似不同点在于设置一个 map 保存结果递归的时候先在 map 中查找如果该字符串已经计算过那么直接返回保存的结果。
代码
class Solution {
public:unordered_mapstring, vectorint mp;vectorint diffWaysToCompute(string expression) {if(mp.find(expression) ! mp.end()) return mp.find(expression) - second;vectorint ans, left, right;int flag 0; int n expression.size();for(int i0; in; i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag 1; // flag1说明string是表达式flag0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left diffWaysToCompute(string(expression, 0, i));right diffWaysToCompute(string(expression, i1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] ) ans.push_back(l r);if(expression[i] -) ans.push_back(l - r);if(expression[i] *) ans.push_back(l * r);}}}}if(flag 0){// expression 只是一个数字// {int} - vectorintreturn {stoi(expression)};}mp[expression] ans;return ans;}
};解法三动态规划
对于表达式 expression 需要做预处理「把每个数字转为 int 存起来同时运算符也存起来」。
这样子将得到两个数组以 2 * 3 - 4 * 5 为例存起来的数字是 numList [2 3 4 5]存起来的运算符是 opList [*, -, *]。
状态定义
dp[i][j] 表示从第 i 个数字到第 j 个数字从 0 开始计数范围内表达式的所有解。
如 dp[1][3]表示第 1 个数字 3 到 第 3 个数字5范围内表达式 3 - 4 * 5 的所有解。
状态转移方程
有了一个数字的所有解初始化就可以求出两个数字的所有解。
有了两个数字的所有解三个数字的所有解就和解法一求法一样。
把三个数字分成两部分将两部分的解两两组合起来即可。
对于两部分之间的运算符因为表达式是一个数字一个运算符所以运算符的下标就是左部分最后一个数字的下标。
对于 2 * 3 - 4 * 5 存起来的数字是 numList [2 3 4 5] 存起来的运算符是 opList [*, -, *]。
假设要求 dp[1][3]也就是计算 3 - 4 * 5 的解 分成 3 和 4 * 5 两部分3 对应的下标是 1 对应的运算符就是 opList[1] - 也就是计算 3 - 20 -17 分成 3 - 4 和 5 两部分4 的下标是 2 对应的运算符就是 opList[2] *。 也就是计算 -1 * 5 -5 所以 dp[1][3] [-17 -5] 。
四个、五个… 都可以分成两部分然后通过之前的解求出来。
直到包含了所有数字的解求出来。
初始化
对范围内只有一个数字的情况进行初始化
dp[0][0] 2, dp[1][1] 3, dp[2][2] 4, dp[3][3] 5;
返回的最终结果
最终返回第 0 个数字到最后一个数字范围内表达式的所有解即 dp[0][n-1]
代码
class Solution {
public:vectorint diffWaysToCompute(string expression) {vectorint numList;vectorchar opList;// 对 expression 预处理int num 0;for(char ch : expression){if(!isdigit(ch)){numList.push_back(num);num 0;opList.push_back(ch);}else{num num * 10 ch - 0;}}numList.push_back(num);int n numList.size();vectorvectorvectorint dp(n, vectorvectorint(n));// dp数组初始化for(int i0; in; i){dp[i][i].push_back(numList[i]);}// 从2个数字遍历到n个数字for(int k2; kn; k){// 开始遍历的下标for(int i0; in; i){// 结束遍历的下标int j i k - 1;if(j n){// 越界break;}vectorint ans;// 以s作为分隔点分成左右两部分遍历for(int si; sj; s){vectorint left dp[i][s];vectorint right dp[s1][j];// 遍历左边部分的所有结果值for(auto x : left){// 遍历右边部分的所有结果值for(auto y : right){// 根据操作符对所有结果进行组合// 操作符下标就是左边部分最后一个数字的下标char op opList[s];if(op ) ans.push_back(x y);else if(op -) ans.push_back(x - y);else if(op *) ans.push_back(x * y);}}}dp[i][j] ans;}}return dp[0][n-1];}
};
