电子商务网站建设 教学大纲,wordpress记事本插件,长春建站模板搭建,网站 系统 的开发技术1. 解题
给定一个含有数字和运算符的字符串#xff0c;为表达式添加括号#xff0c;改变其运算优先级以求出不同的结果。 你需要给出所有可能的组合的结果。有效的运算符号包含 , - 以及 * 。
示例 1:
输入: 2-1-1
输出: [0, 2]
解释:
((2-1)-1) 0
(2-(1-1)…1. 解题
给定一个含有数字和运算符的字符串为表达式添加括号改变其运算优先级以求出不同的结果。 你需要给出所有可能的组合的结果。有效的运算符号包含 , - 以及 * 。
示例 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/different-ways-to-add-parentheses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. DP解题
dp[i][j]存储区间[i,j]内可能的结果数值先初始化dp[i][i],dp[i][i1]然后按照区间长度 len 不断加大 dp[i][ilen] sum(dp[i][j] op dp[j1][ilen]) j 在区间内遍历左右的数组合进行运算的值存入dp[i][ilen]
class Solution {
public:vectorint diffWaysToCompute(string input) {int i, j, k, num0;vectorint arr;//数字存起来vectorchar op;//操作符存起来for(i 0; i input.size(); i){if(!isdigit(input[i])){arr.push_back(num);op.push_back(input[i]);num 0;}elsenum num*10input[i]-0;}arr.push_back(num);//最后一个数字int n arr.size();vectorvectorvectorint dp(n,vectorvectorint(n));for(i 0; i n-1; i){dp[i][i] {arr[i]};//初始化dp[i][i]if(op[i])dp[i][i1] {arr[i]arr[i1]};//初始化dp[i][i1]else if(op[i]-)dp[i][i1] {arr[i]-arr[i1]};else if(op[i]*)dp[i][i1] {arr[i]*arr[i1]};}dp[n-1][n-1] {arr[n-1]};//初始化dp[i][i]for(int len 2; len n; len){ //按长度dpfor(i 0; i n-len; i){ //左端点for(j i; j ilen; j){ //中间端点for(int dl : dp[i][j]){ //左边的数值for(int dr : dp[j1][ilen])//左边的数值if(op[j])dp[i][ilen].push_back(dldr);else if(op[j]-)dp[i][ilen].push_back(dl-dr);else if(op[j]*)dp[i][ilen].push_back(dl*dr);}}}}sort(dp[0][n-1].begin(),dp[0][n-1].end());return dp[0][n-1];}
};
