Leetcode 282 给表达式添加运算符+-*运算暴搜处理

tech2023-07-24  113

+,-,*有一种特别直接的处理方法是直接算,保存一个答案ans,pre,遇到运算符就算,遇到乘法的时候就先把之前算的减掉ans-pre+pre*cur,就这样处理即可。

typedef long long LL; class Solution { public: vector<string> addOperators(string num, int target) { string expression; helper(num,target,0,0,0,expression); return res; } vector<string> res; void helper(string num, int target, int index, LL ans, LL pre, string expression){ if(index==num.size()){ if(target==(int)ans) res.push_back(expression); return; } for(int i=index;i<num.size();i++){ string s = num.substr(index, i - index + 1); // 从index向后取出对应长度的新字符串 if(s.size() > 1 && s[0] == '0') return; // 如果第一位是0的两位数,那么跳过 long cur = stol(s); if(index==0) helper(num,target,i+1,ans+cur,cur,expression+s); else{ helper(num,target,i+1,ans+cur,cur,expression+"+"+s); helper(num,target,i+1,ans-cur,-cur,expression+"-"+s); helper(num,target,i+1,ans- pre + pre * cur, pre*cur,expression+"*"+s); } } } };

将传值改成传引用,并加入回溯处理

typedef long long LL; class Solution { public: vector<string> addOperators(string num, int target) { string expression; helper(num,target,0,0,0,expression); return res; } vector<string> res; void helper(string num, int target, int index, LL ans, LL pre, string expression){ if(index==num.size()){ if(target==(int)ans) res.push_back(expression); return; } for(int i=index;i<num.size();i++){ string s = num.substr(index, i - index + 1); // 从index向后取出对应长度的新字符串 if(s.size() > 1 && s[0] == '0') return; // 如果第一位是0的两位数,那么跳过 long cur = stol(s); if(index==0) helper(num,target,i+1,ans+cur,cur,expression+s); else{ helper(num,target,i+1,ans+cur,cur,expression+"+"+s); helper(num,target,i+1,ans-cur,-cur,expression+"-"+s); helper(num,target,i+1,ans- pre + pre * cur, pre*cur,expression+"*"+s); } } } };

 

最新回复(0)