leetcode 241 Different Ways to Add Parentheses
2602 ワード
新しい問題のようですが、テーマは以下の通りです.
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are
Example 1
Input:
Output:
Example 2
Input:
Output:
考え方は以下の通りである.
1+2+3+4+5を考慮すると、まず1つの演算子を計算することができ、得られたサブ式3+3+4+5は再帰を利用し、戻ると式の戻り結果は1+2+3+4+5の一部であり、1つの問題に注意し、式1+2+3+4+5については、まず1+2を計算してから3+4を計算し、先に3+4を計算して1+2を計算し、カッコを追加する上で同じ(1+2)+(3+4)+5を表現する.したがって、再帰的には、最後に計算された結果の前の最初の演算子の後の文字のみが計算されます.
コードは次のとおりです.
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are
+
, -
and *
. Example 1
Input:
"2-1-1"
. ((2-1)-1) = 0
(2-(1-1)) = 2
Output:
[0, 2]
Example 2
Input:
"2*3-4*5"
(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
Output:
[-34, -14, -10, -10, 10]
, , , 。
考え方は以下の通りである.
1+2+3+4+5を考慮すると、まず1つの演算子を計算することができ、得られたサブ式3+3+4+5は再帰を利用し、戻ると式の戻り結果は1+2+3+4+5の一部であり、1つの問題に注意し、式1+2+3+4+5については、まず1+2を計算してから3+4を計算し、先に3+4を計算して1+2を計算し、カッコを追加する上で同じ(1+2)+(3+4)+5を表現する.したがって、再帰的には、最後に計算された結果の前の最初の演算子の後の文字のみが計算されます.
コードは次のとおりです.
class Solution {
public:
vector<int> dWtC(vector<int> num,vector<char> ch,int x)
{
vector<int> v;
if (ch.size() == 0)
{
v.push_back(num[0]);
return v;
}
if (ch.size() == 1)
{
int a;
switch (ch[0])
{
case '+':a = num[0] + num[1]; break;
case '-':a = num[0] - num[1]; break;
case '*':a = num[0] * num[1]; break;
default:break;
}
v.push_back(a);
return v;
}
else
{
for (int i = x; i < ch.size(); i++)
{
vector<int> nn = num;
vector<char> cc = ch;
switch (cc[i])
{
case '+':nn[i+1] = num[i] + num[i+1]; break;
case '-':nn[i + 1] = num[i] - num[i + 1]; break;
case '*':nn[i + 1] = num[i] * num[i + 1]; break;
default:break;
}
vector<int>::iterator it_num = nn.begin()+i ;
vector<char>::iterator it_ch = cc.begin() + i;
nn.erase(it_num);
cc.erase(it_ch);
vector<int> vv;
if (i==0)
vv = dWtC(nn,cc,0);
else
vv = dWtC(nn, cc, i-1);
for (int j = 0; j < vv.size(); j++)
v.push_back(vv[j]);
}
sort(v.begin(),v.end());
return v;
}
}
vector<int> diffWaysToCompute(string input)
{
vector<int> v;
if (input.length() == 0)
return v;
vector<int> num;
vector<char> ch;
int a=0;
for (int i = 0; i < input.length(); i++)
{
if (input[i] == '+' || input[i] == '-' || input[i] == '*')
{
num.push_back(a);
ch.push_back(input[i]);
a = 0;
}
else
a =10*a+(input[i]-'0');
}
num.push_back(a);
return dWtC(num, ch,0);
}
};