题目
题解： 如标题，其实就是暴搜啦
代码语言：javascript复制class Solution {
public:
vector<string> ans;
int target2;
vector<string> addOperators(string num, int target) {
if(num.length()==0)
return ans;
target2 = target;
string s="";
s =num[0];
fun(num,s,0,-1,-1,num[0]-'0','.','.');
return ans;
}
void fun(string num,string res,int pos,int last,int pre,int root,char operate,char operate2)
{
if(pos==num.length()-1)
{
if(operate!='.'&&operate2!='.')
{
if(operate2=='*')
{
if(compute(root,compute(pre,last,'*'),operate)==target2)
{
ans.push_back(res);
}
}
else
{
if(compute(compute(root,pre,operate),last,operate2)==target2)
{
ans.push_back(res);
}
}
}
else if(operate!='.'&&operate2=='.')
{
if(compute(root,pre,operate)==target2)
ans.push_back(res);
}
else
{
if(root==target2)
ans.push_back(res);
}
return;
}
if(operate=='.')
{
if(root!=0&&((long long int)root)*10 (long long int)(num[pos 1]-'0') <= INT_MAX)
{
fun(num,res num[pos 1],pos 1,-1,-1,root*10 (num[pos 1]-'0'),'.','.');
}
fun(num,res " " num[pos 1],pos 1,-1,num[pos 1]-'0',root,' ','.');
fun(num,res "-" num[pos 1],pos 1,-1,num[pos 1]-'0',root,'-','.');
fun(num,res "*" num[pos 1],pos 1,-1,num[pos 1]-'0',root,'*','.');
}
else if(operate!='.'&&operate2=='.')
{
if(pre!=0&&((long long int)pre)*10 (long long int)(num[pos 1]-'0') <= INT_MAX)
{
fun(num,res num[pos 1],pos 1,-1,pre*10 (num[pos 1]-'0'),root,operate,'.');
}
fun(num,res " " num[pos 1],pos 1,num[pos 1]-'0',pre,root,operate,' ');
fun(num,res "-" num[pos 1],pos 1,num[pos 1]-'0',pre,root,operate,'-');
fun(num,res "*" num[pos 1],pos 1,num[pos 1]-'0',pre,root,operate,'*');
}
else
{
if(last!=0&&((long long int)last)*10 (long long int)(num[pos 1]-'0') <= INT_MAX)
{
fun(num,res num[pos 1],pos 1,last*10 (num[pos 1]-'0'),pre,root,operate,operate2);
}
if(operate=='*')
{
fun(num,res " " num[pos 1],pos 1,num[pos 1]-'0',last,root*pre,operate2,' ');
fun(num,res "-" num[pos 1],pos 1,num[pos 1]-'0',last,root*pre,operate2,'-');
fun(num,res "*" num[pos 1],pos 1,num[pos 1]-'0',last,root*pre,operate2,'*');
}
else if(operate2=='*')
{
fun(num,res " " num[pos 1],pos 1,num[pos 1]-'0',pre*last,root,operate,' ');
fun(num,res "-" num[pos 1],pos 1,num[pos 1]-'0',pre*last,root,operate,'-');
fun(num,res "*" num[pos 1],pos 1,num[pos 1]-'0',pre*last,root,operate,'*');
}
else
{
fun(num,res " " num[pos 1],pos 1,num[pos 1]-'0',last,operate==' '?root pre:root-pre,operate2,' ');
fun(num,res "-" num[pos 1],pos 1,num[pos 1]-'0',last,operate==' '?root pre:root-pre,operate2,'-');
fun(num,res "*" num[pos 1],pos 1,num[pos 1]-'0',last,operate==' '?root pre:root-pre,operate2,'*');
}
}
}
int compute(int x,int y,char operate)
{
if(operate==' ')
return x y;
else if(operate=='-')
return x-y;
else
{
if((long long int)x*(long long int)y>INT_MAX)
return -1;
return x*y;
}
}
};
