南京模板做网站,网站建设要架服务器,嘉兴有哪些做网站的公司,素材之家282. 给表达式添加运算符#xff08;困难#xff09;
题目描述#xff1a; 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target #xff0c;在 num 的数字之间添加 二元 运算符#xff08;不是一元#xff09;、- 或 * #xff0c;返回 所有 能够得到 targe…282. 给表达式添加运算符困难
题目描述 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target 在 num 的数字之间添加 二元 运算符不是一元、- 或 * 返回 所有 能够得到 target 的表达式。
注意返回表达式中的操作数 不应该 包含前导零。
考察重点针对此类返回所有情况的问题直接使用DFS解决。 public ListString addOperators(String num, int target) {ListString res new ArrayList();if (num null || num.length() 0) {return res;}help(num, target, 0, 0, 0, , res);return res;}private void help(String num, int target, long curRes, long diff, int start, String curExp, ListString expressions) {if (start num.length() (long)target curRes) {expressions.add(new String(curExp));}for (int i start; i num.length(); i) {String cur num.substring(start, i 1);if (cur.length() 1 cur.charAt(0) 0) { //按照题目要求得到的操作数不应该包含前导0即0只能以数字0加入表达式break;}if (curExp.length() 0) {help(num, target, curRes Long.valueOf(cur), Long.valueOf(cur), i 1, curExp cur, expressions);help(num, target, curRes - Long.valueOf(cur), -Long.valueOf(cur), i 1, curExp - cur, expressions);help(num, target, (curRes - diff) diff * Long.valueOf(cur), diff * Long.valueOf(cur),i 1, curExp * cur, expressions);} else {help(num, target, Long.valueOf(cur), Long.valueOf(cur), i 1, cur, expressions);}}}
