Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/09/19 12:19)推噓1(1推 0噓 0→)留言1則, 1人參與討論串879/1550 (看更多)
題目:241. Different Ways to Add Parentheses
給你一個字串，代表一個運算式，求當我們任意添加夸號將所有數和運算子分群後
的計算結果的所有可能，例如"2-1-1"有"((2-1)-1)"和"(2-(1-1))"兩種分群運算可能
思路:
問題可以等價成給你一串運算式，我可以產生多少顆相異的expression tree和其運算
結果，因此也可以轉換成當初考研究所時準備的min matrix multiplication問題，但
對應的DP表格dp[i][[j]=運算式第i個數字到第j個數字的相乘可能結果，而dp[j][j+i]=
所有元素(dp[j][j+i-q])各自和所有元素(dp[j+i-q+1][j+i])經過第[j+i-q]個運算子
進行運算的全部產生元素，最後回傳dp[0][number of number in expression-1]即可
vector<int> diffWaysToCompute(string expression) {
vector<int> thedit;
vector<char> theop;
string temp="";
int yp=0;
while(yp<expression.size()){
if(expression[yp]>47){
temp+=expression[yp];
}
else{
thedit.push_back(stoi(temp));
temp="";
theop.push_back(expression[yp]);
}
yp++;
}
thedit.push_back(stoi(temp));
vector<vector<vector<int>>>
pre_ans(thedit.size(),vector<vector<int>>(thedit.size(),vector<int>()));
for(int i=0;i<thedit.size();++i){
pre_ans[i][i].push_back(thedit[i]);
}
for(int i=1;i<thedit.size();++i){
for(int j=0;j<thedit.size()-i;++j){
//we now edit pre_ans[j][j+i], which include all sol for(j to
j+i)
for(int q=i;q>0;--q){
for(auto k:pre_ans[j][j+i-q]){
for(auto h:pre_ans[j+i-q+1][j+i]){
if(theop[j+i-q]=='*'){
pre_ans[j][j+i].push_back(k*h);
}
else if(theop[j+i-q]=='-'){
pre_ans[j][j+i].push_back(k-h);
}
else if(theop[j+i-q]=='+'){
pre_ans[j][j+i].push_back(k+h);
}
}
}
}
}
}
return pre_ans[0][thedit.size()-1];
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.196.198 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726719594.A.00E.html
推
09/19 14:13,
1年前
, 1F
09/19 14:13, 1F
討論串 (同標題文章)
完整討論串 (本文為第 879 之 1550 篇)：