[数据结构与算法]每日一题-给表达式添加运算符

Leetcode

题意：就是给相应长度的数字间添加操作符。
思路：首先想到的是回溯法，然后去枚举+，-，*，无，四种情况，但是后来测试的时候发现。。。tmd可以两位数的（怪我眼瞎！审题不仔细）。然后看了下题解，发现也是神奇的回溯法。真的优美（我的天，我啥时候能写出来这么优美的代码啊，呜呜呜）。题解的思路也差不多，只是外加了一层数字拼接模拟。然后里面套了四个dfs。emm，多练习！坚持！
然后代码，是题解的代码。

class Solution {

    int n;
    String num;
    int target;
    List<String> list;


    public void dfs(StringBuilder expr,int i,long res,long mul){
        if(i==n){
            if(res == target){
                list.add(expr.toString());
            }
            return;
        }

        int index = expr.length();//记录当前还没加符号的位置，方便回溯
        if(i>0)expr.append(0);//控制符号的

        long val =0;
        for(int j=i; j<n&& (j==i || num.charAt(i)!='0');j++){//选数字长度。然后0是不能在第一位的，也就是不能有前导零。
            val = val*10+num.charAt(j)-'0';
            expr.append(num.charAt(j));//将数字添加进去
            if(i==0){
                dfs(expr,j+1,val,val);//这个是控制第一位数的
            }
            else{
            //四种情况，妙妙妙！
                expr.setCharAt(index,'+');
                dfs(expr,j+1,res+val,val);
                expr.setCharAt(index,'-');
                dfs(expr,j+1,res-val,-val);
                expr.setCharAt(index,'*');
                dfs(expr,j+1,res-mul+mul*val,mul*val);
            }
        }

        expr.setLength(index);//回溯
    }


    public List<String> addOperators(String num, int target) {
        this.n = num.length();
        this.num = num;
        this.target = target;
        StringBuilder sb = new StringBuilder();
        list = new ArrayList<>();
        dfs(sb,0,0,0);
        return list;
    }
}