?LeetCode刷題實(shí)戰(zhàn)241：為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
示例
示例 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
解題
dp[i][j]存儲(chǔ)區(qū)間[i,j]內(nèi)可能的結(jié)果數(shù)值
先初始化dp[i][i],dp[i][i+1]
然后按照區(qū)間長度 len 不斷加大 dp[i][i+len] = sum(dp[i][j] op dp[j+1][i+len]) j 在區(qū)間內(nèi)遍歷，左右的數(shù)組合進(jìn)行運(yùn)算的值，存入dp[i][i+len]
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
int i, j, k, num=0;
vector<int> arr;//數(shù)字存起來
vector<char> op;//操作符存起來
for(i = 0; i < input.size(); ++i)
{
if(!isdigit(input[i]))
{
arr.push_back(num);
op.push_back(input[i]);
num = 0;
}
else
num = num*10+input[i]-'0';
}
arr.push_back(num);//最后一個(gè)數(shù)字
int n = arr.size();
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n));
for(i = 0; i < n-1; ++i)
{
dp[i][i] = {arr[i]};//初始化dp[i][i]
if(op[i]=='+')
dp[i][i+1] = {arr[i]+arr[i+1]};//初始化dp[i][i+1]
else if(op[i]=='-')
dp[i][i+1] = {arr[i]-arr[i+1]};
else if(op[i]=='*')
dp[i][i+1] = {arr[i]*arr[i+1]};
}
dp[n-1][n-1] = {arr[n-1]};//初始化dp[i][i]
for(int len = 2; len < n; ++len)
{ //按長度dp
for(i = 0; i < n-len; ++i)
{ //左端點(diǎn)
for(j = i; j < i+len; ++j)
{ //中間端點(diǎn)
for(int dl : dp[i][j])
{ //左邊的數(shù)值
for(int dr : dp[j+1][i+len])//左邊的數(shù)值
if(op[j]=='+')
dp[i][i+len].push_back(dl+dr);
else if(op[j]=='-')
dp[i][i+len].push_back(dl-dr);
else if(op[j]=='*')
dp[i][i+len].push_back(dl*dr);
}
}
}
}
sort(dp[0][n-1].begin(),dp[0][n-1].end());
return dp[0][n-1];
}
};