2021-09-06：给表达式添加运算符。给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元） 、- 或 * ，返回所有能够得到目标值的表达式。力扣282。
福大大 答案2021-09-06：
递归。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
num := "123"
target := 6
ret := addOperators(num, target)
fmt.Println(ret)
}
func addOperators(num string, target int) []string {
ret := make([]string, 0)
if len(num) == 0 {
return ret
}
// 沿途的数字拷贝和 - * 的决定，放在path里
path := make([]byte, len(num)*2-1)
// num -> char[]
digits := []byte(num)
n := 0
for i := 0; i < len(digits); i { // 尝试0~i前缀作为第一部分
n = n*10 int(digits[i]) - '0'
path[i] = digits[i]
dfs(&ret, &path, i 1, 0, n, &digits, i 1, target) // 后续过程
if n == 0 {
break
}
}
return ret
}
// char[] digits 固定参数，字符类型数组，等同于num
// int target 目标
// char[] path 之前做的决定，已经从左往右依次填写的字符在其中，可能含有'0'~'9' 与 * -
// int len path[0..len-1]已经填写好，len是终止
// int pos 字符类型数组num, 使用到了哪
// left -> 前面固定的部分 cur -> 前一块
// 默认 left cur ...
func dfs(res *[]string, path *[]byte, len2 int, left int, cur int, num *[]byte, index int, aim int) {
if index == len(*num) {
if left cur == aim {
//res.add(new String(path, 0, len));
*res = append(*res, string((*path)[0:len2]))
}
return
}
n := 0
j := len2 1
for i := index; i < len(*num); i { // pos ~ i
// 试每一个可能的前缀，作为第一个数字！
// num[index...i] 作为第一个数字！
n = n*10 int((*num)[i]) - '0'
(*path)[j] = (*num)[i]
j
(*path)[len2] = ' '
dfs(res, path, j, left cur, n, num, i 1, aim)
(*path)[len2] = '-'
dfs(res, path, j, left cur, -n, num, i 1, aim)
(*path)[len2] = '*'
dfs(res, path, j, left, cur*n, num, i 1, aim)
if (*num)[index] == '0' {
break
}
}
}执行结果如下：
图片左神java代码
