|
给定一个仅包含数字0-9的字符串num和一个目标值整数target，在num的数字之间添加二元运算符（不是一元）+、-或*，返回所有能够得到目标值的表达式。 示例 1: 输入: num = "123", target = 6 输出: ["1+2+3", "1*2*3"]
示例 2: 输入: num = "232", target = 8 输出: ["2*3+2", "2+3*2"]
示例 3:
输入: num = "105", target = 5 输出: ["1*0+5","10-5"]
示例 4:
输入: num = "00", target = 0 输出: ["0+0", "0-0", "0*0"]
示例 5: 输入: num = "3456237490", target = 9191 输出: []
提示： 1<=num.length<=10 num仅含数字 -2^31<=target<=2^31-1
这题是让在数字之间添加“+”，“-”，“*”三种符号，变成一个算术表达式，并且让算术表达式的结果等于target。解题思路就是使用回溯算法列举所有可构成的算术表达式，然后计算他们的值。 关于回溯算法之前也讲过多次，也可以看下450，什么叫回溯算法，一看就会，一写就废。这题我们可以把它看做是一颗n叉树，除了第一个数字以外，其他的每个数字都可以在他的前面添加“+”，“-”，“*”这三种符号，这里以示例一为例画个图来看一下。 
来看个视频
我们可以看到这题和566，DFS解目标和问题有点相似，不同的是第566题只能添加“+”和“-”，而这题还可以添加“*”，这里要注意“*”的优先级要比“+”和“-”高。所以在回溯算法中我们需要使用一个变量preNum来记录前面连续相乘的积，还有一点就是这里的数字需要我们截取，截取的时候数字必须是有效的，也就是数字的最前面不能是0，比如“05”这种就是无效数字。来看下代码 public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
dfs(res, num, target, 0, 0, 0, "");
return res;
}
/**
* @param res 返回的结果
* @param num 字符串num
* @param target 目标值target
* @param index 访问到字符串的第几个字符
* @param preNum 前面的连续乘积（乘法的时候会用到）
* @param sum 表达式前面计算得到的和
* @param path 算术表达式，可以看做n叉树的路径
*/
private void dfs(List<String> res, String num, int target, int index, long preNum, long sum, String path) {
//字符串num中所有元素都遍历完了，要指针遍历
if (index >= num.length()) {
//如果表达式的值等于target，说明找到了一个合适的表达式，
//就把他加入到集合res中
if (sum == target) {
res.add(path);
}
return;
}
for (int i = index; i < num.length(); i++) {
//类似于05，07这样以0开头的数字要过滤掉
if (i != index && num.charAt(index) == '0')
break;
//截取字符串，转化为数字
long number = Long.parseLong(num.substring(index, i + 1));
if (index == 0) {
//因为第一个数字前面是没有符号的，所以要单独处理
dfs(res, num, target, i + 1, number, number, "" + number);
} else {
//在当前数字number前面可以添加"+","-","*"三种符号。
//数字number前添加"+"
dfs(res, num, target, i + 1, number, sum + number, path + "+" + number);
//数字number前添加"-"
dfs(res, num, target, i + 1, -number, sum - number, path + "-" + number);
//数字number前添加"*"
dfs(res, num, target, i + 1, preNum * number,
sum + preNum * number - preNum, path + "*" + number);
}
}
}
|
