题目链接：https://www.nowcoder.com/practice/fdaee292bdaf4a7eb686c8ce72b2f3e1
题目描述
给定一个仅包含数字的字符串 num 和一个目标值 target，在 num 的数字之间添加二元运算符 "+" , "-" 或 "*" ,返回所有能够得到目标值的表达式。
数据范围：字符串长度满足1≤n≤10 ， nums 中仅包含数字， |target|≤10^9
示例 1：
输入："123",6
返回值：["1+2+3","1*2*3"]
示例 2：
输入："00",0
返回值：["0+0","0*0","0-0"]
解题代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param target int整型
* @return string字符串一维数组
*/
int n;
String num;
int target;
List<String> ans;
public String[] addOpt (String num, int target) {
// write code here
this.n = num.length();
this.num = num;
this.target = target;
this.ans = new ArrayList<String>();
StringBuilder expr = new StringBuilder();
backtrack(expr, 0, 0, 0);
return ans.toArray(new String[ans.size()]);
}
public void backtrack(StringBuilder expr, int i, long res, long mul) {
if (i == n) {
if (res == target) {
ans.add(expr.toString());
}
return;
}
int signIndex = expr.length();
if (i > 0) {
expr.append(0); // 占位，下面填充符号
}
long val = 0;
// 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
for (int j = i; j < n && (j == i || num.charAt(i) != '0'); ++j) {
val = val * 10 + num.charAt(j) - '0';
expr.append(num.charAt(j));
if (i == 0) { // 表达式开头不能添加符号
backtrack(expr, j + 1, val, val);
} else { // 枚举符号
expr.setCharAt(signIndex, '+');
backtrack(expr, j + 1, res + val, val);
expr.setCharAt(signIndex, '-');
backtrack(expr, j + 1, res - val, -val);
expr.setCharAt(signIndex, '*');
backtrack(expr, j + 1, res - mul + mul * val, mul * val);
}
}
expr.setLength(signIndex);
}
}
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为:
2022/08/11 11:13:15
如果你觉得文章对你有帮助，那就请作者喝杯咖啡吧☕
0
条评论
