NC217 给表达式添加运算符

题目链接：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