首页 > 代码库 > Expression Add Operators
Expression Add Operators
Given a string that contains only digits 0-9
and a target value, return all possibilities to add binary operators (not unary) +
, -
, or *
between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> []
其实这题是很简单的,就是用DFS找出所有可能性,只是最最麻烦的是怎么处理前面部分是加减,后面部分是乘的情况。我本来是用逆波兰表达式来计算的,但是下面的解法更方便。
From: https://segmentfault.com/a/1190000003797204
1 public class Solution { 2 3 List<String> res = new ArrayList<String>(); 4 5 public List<String> addOperators(String num, int target) { 6 helper(num, target, "", 0, 0); 7 return res; 8 } 9 10 private void helper(String num, int target, String tmp, long currRes, long prevNum) { 11 // 如果计算结果等于目标值,且所有数都用完了,则是有效结果 12 if (currRes == target && num.length() == 0) { 13 String exp = new String(tmp); 14 res.add(exp); 15 return; 16 } 17 // 搜索所有可能的拆分情况 18 for (int i = 1; i <= num.length(); i++) { 19 String currStr = num.substring(0, i); 20 // 对于前导为0的数予以排除 21 if (currStr.length() > 1 && currStr.charAt(0) == ‘0‘) { 22 // 这里是return不是continue 23 return; 24 } 25 // 得到当前截出的数 26 long currNum = Long.parseLong(currStr); 27 // 去掉当前的数,得到下一轮搜索用的字符串 28 String next = num.substring(i); 29 // 如果不是第一个字母时,可以加运算符,否则只加数字 30 if (tmp.length() != 0) { 31 // 乘法 32 helper(next, target, tmp + "*" + currNum, (currRes - prevNum) + prevNum * currNum, prevNum * currNum); 33 // 加法 34 helper(next, target, tmp + "+" + currNum, currRes + currNum, currNum); 35 // 减法 36 helper(next, target, tmp + "-" + currNum, currRes - currNum, -currNum); 37 } else { 38 // 第一个数 39 helper(next, target, currStr, currNum, currNum); 40 } 41 42 } 43 } 44 }
Expression Add Operators
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。