Golang | Leetcode Golang题解之第282题给表达式添加运算符
题目:
题解:
func addOperators(num string, target int) (ans []string) {
n := len(num)
var backtrack func(expr []byte, i, res, mul int)
backtrack = func(expr []byte, i, res, mul int) {
if i == n {
if res == target {
ans = append(ans, string(expr))
}
return
}
signIndex := len(expr)
if i > 0 {
expr = append(expr, 0) // 占位,下面填充符号
}
// 枚举截取的数字长度(取多少位),注意数字可以是单个 0 但不能有前导零
for j, val := i, 0; j < n && (j == i || num[i] != '0'); j++ {
val = val*10 + int(num[j]-'0')
expr = append(expr, num[j])
if i == 0 { // 表达式开头不能添加符号
backtrack(expr, j+1, val, val)
} else { // 枚举符号
expr[signIndex] = '+'; backtrack(expr, j+1, res+val, val)
expr[signIndex] = '-'; backtrack(expr, j+1, res-val, -val)
expr[signIndex] = '*'; backtrack(expr, j+1, res-mul+mul*val, mul*val)
}
}
}
backtrack(make([]byte, 0, n*2-1), 0, 0, 0)
return
}
原文地址:https://blog.csdn.net/weixin_66442839/article/details/140651275
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!