Problem
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.
Example 1:
Input: num = "123", target = 6
Output: ["1+2+3", "123"]
Example 2:
Input: num = "232", target = 8
Output: ["23+2", "2+32"]
Example 3:
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Example 4:
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
Example 5:
Input: num = "3456237490", target = 9191
Output: []
class Solution { public ListSave path to StringBuilderaddOperators(String num, int target) { List res = new ArrayList<>(); if (num == null || num.length() == 0) return res; dfs(num, "", 0, target, res, 0, 0); return res; } private void dfs(String num, String temp, int index, int target, List res, long val, long multi) { if (index == num.length()) { if (val == target) res.add(temp); return; } for (int i = index; i < num.length(); i++) { if (i != index && num.charAt(index) == "0") break; long cur = Long.parseLong(num.substring(index, i+1)); if (index == 0) { dfs(num, temp+cur, i+1, target, res, cur, cur); } else { dfs(num, temp+"+"+cur, i+1, target, res, val+cur, cur); dfs(num, temp+"-"+cur, i+1, target, res, val-cur, -cur); dfs(num, temp+"*"+cur, i+1, target, res, val-multi+multi*cur, multi*cur); } } } }
class Solution { public ListUse char[] to store num and use StringBuilderaddOperators(String num, int target) { List res = new ArrayList<>(); dfs(num, 0, 0, target, 0, new StringBuilder(), res); return res; } private void dfs(String num, int index, long value, int target, long multi, StringBuilder sb, List res) { if (index == num.length()) { if (value == target) res.add(sb.toString()); return; } for (int i = index; i < num.length(); i++) { if (num.charAt(index) == "0" && i != index) break; long cur = Long.parseLong(num.substring(index, i+1)); int len = sb.length(); if (index == 0) { sb.append(cur); dfs(num, i+1, cur, target, cur, sb, res); sb.setLength(len); } else { sb.append("+").append(cur); dfs(num, i+1, value+cur, target, cur, sb, res); sb.setLength(len); sb.append("-").append(cur); dfs(num, i+1, value-cur, target, -cur, sb, res); sb.setLength(len); sb.append("*").append(cur); dfs(num, i+1, value-multi+multi*cur, target, multi*cur, sb, res); sb.setLength(len); } } } }
class Solution { public ListaddOperators(String num, int target) { List res = new ArrayList<>(); dfs(num.toCharArray(), 0, new StringBuilder(), 0, 0, target, res); return res; } private void dfs(char[] digits, int index, StringBuilder sb, long value, long multi, int target, List res) { if (index == digits.length) { if (value == target) res.add(sb.toString()); return; } for (int i = index; i < digits.length; i++) { if (digits[index] == "0" && i != index) break; long cur = Long.parseLong(new String(digits, index, i-index+1)); int len = sb.length(); if (index == 0) { sb.append(cur); dfs(digits, i+1, sb, cur, cur, target, res); sb.setLength(len); } else { sb.append("+").append(cur); dfs(digits, i+1, sb, value+cur, cur, target, res); sb.setLength(len); sb.append("-").append(cur); dfs(digits, i+1, sb, value-cur, -cur, target, res); sb.setLength(len); sb.append("*").append(cur); dfs(digits, i+1, sb, value-multi+multi*cur, multi*cur, target, res); sb.setLength(len); } } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/72347.html
摘要:题目链接动态规划问题,最后要求全部满足条件的。还有个问题是取数字的时候可能超过的范围,用来处理。的做法,讨论切分点从到,本质和做法是一样的,复杂度也不会降低。关键是求值,又变成原来的问题了,所以这题感觉不能加。 282. Expression Add Operators 题目链接:https://leetcode.com/problems... 动态规划问题,最后要求全部满足条件的pa...
摘要:唯一需要注意的就是乘法的情况,产生出,到达的时候,算出不包含的值,这里是,是乘号以前的算式值,算乘法部分。 Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * be...
摘要:双栈法四则运算括号复杂度时间空间思路算符优先算法,核心维护两个栈,一个操作数栈,一个操作符栈。 Basic Calculator 2 Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers...
摘要:问题在于如何将问题拆分成多次搜索。然而,乘法如何处理呢这里我们需要用一个变量记录乘法当前累乘的值,直到累乘完了,遇到下一个加号或减号再将其算入计算结果中。这样的计算结果就是。注意第一次搜索不添加运算符,只添加数字,就不会出现这种表达式了。 Expression Add Operators Given a string that contains only digits 0-9 and...
Problem Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and e...
阅读 658·2021-11-23 09:51
阅读 3258·2021-10-11 10:58
阅读 15407·2021-09-29 09:47
阅读 3529·2021-09-01 11:42
阅读 1281·2019-08-29 16:43
阅读 1832·2019-08-29 15:37
阅读 2089·2019-08-29 12:56
阅读 1718·2019-08-28 18:21