欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

282. Expression Add Operators

程序员文章站 2022-07-14 22:33:17
...

题目理解

输入:一个字符串num,一个int target。输入num只包含数字。
规则:可以给num中包含的数字之间任务添加二目运算符:+ - *,使得表达式的值等于target。
输出:所有可能的符合条件的表达式。

示例1:num=“123”, target=6
输出:[“1+2+3”, “123”]

示例2:num=“232”, target=8
输出:[“23+2", "2+32”]

示例3:num = “105”, target = 5
输出: [“1*0+5”,“10-5”]

分析

从示例中可以看到我们可以在每一个数字之间加运算符,而数字可以是一位数字1、2、3,也可以是两位、三位数字:12、32、123。那么我们可以把1和2连在一起认为是第四种操作。

这道题目看了官方的解答和花花酱的视频,依然云里雾里。一直到看了windliang的解法终于想明白了 。

解题思路是回溯法。每次添加一个操作符和一个数字。以num=123为例。下图是部分递归树。每条路径可以获得一个表达式。
282. Expression Add Operators

第一步:dfs获得所有表达式

第一步我们使用dfs遍历打印出所有可能的表达式。注意第一个数字比较特别,只加数字,不加操作符。

class Solution {
    private String num;
    private int target;
    public List<String> addOperators(String num, int target) {
        this.num = num;
        this.target  = target;
        dfs(0,"");
        return null;
    }
    
    private void dfs(int start,String expr){
        if(start == num.length()){
            System.out.println(expr);
            return;
        }
        for(int  i = start ;i<num.length();i++){
            String t = num.substring(start,i+1);
            if(start == 0){
                dfs(i+1,t);
            }else{
                dfs(i+1,expr+"+"+t);
                dfs(i+1,expr+"-"+t);
                dfs(i+1,expr+"*"+t);
            }
            
        }
    }
}

使用num='123’做测试,得到输出1+2+3 1+2-3 1+2*3 1-2+3 1-2-3 1-2*3 1*2+3 1*2-3 1*2*3 1+23 1-23 1*23 12+3 12-3 12*3 123

第二步:计算结果

有了表达式,可以在每次表达式变化的时候计算表达式的结果。运算包括加法、减法、乘法。因为乘法优先级高,最后再处理。我们先看看怎么计算加减法。

先计算加减法

我们在上面递归树的每个节点加一个结果dfs(n,expr,value)。每个节点在计算表达式的值的时候,需要拿上一个表达式的结果与当前数字n做操作。
282. Expression Add Operators

例如计算1+2+3

表达式 上一步value value
1 1
1+2 1 1+2=3
1+2+3 3 3+3=6

例如计算1-2+3

表达式 上一步value value
1 1
1-2 1 1-2=-1
1-2+3 -1 -1+3=2

在计算加减法的时候,只需要保存上一步的表达式的值即可。

class Solution {
    private String num;
    private int target;
    private List<String> result;
    public List<String> addOperators(String num, int target) {
        this.num = num;
        this.target  = target;
        result = new ArrayList<String>();
        dfs(0,"",0);
        return result;
    }
    
    private void dfs(int start,String expr,long value){
        if(start == num.length()){
            System.out.println(expr+" "+value);
            if(value == target){
            }
            return;
        }
        for(int  i = start ;i<num.length();i++){
            String t = num.substring(start,i+1);
         
            long n = Long.parseLong(t);
            if(start == 0){
                dfs(i+1,t,n);
            }else{
                dfs(i+1,expr+"+"+t,value+n);
                dfs(i+1,expr+"-"+t,value-n);
                dfs(i+1,expr+"*"+t,value*n);
            }
            
        }
    }
}

查看打印结果:1+2+3=6 1+2-3=0 1+2*3=9能够发现加法减法是正确的,乘法计算错了。

计算乘法

以1+2*3为例。

表达式 上一步value value
1+2 1 1+2=3
1+2*3 3 3*3=9

这是计算过程。我们不应该先算加法。我们需要记录下上一步的操作数preOperand,先在结果中减去preOperand。然后preOperand在乘以当前数字。即:val-preOperand + preOperand*n=3-2+2x3=7。计算结果正确。

如果上一步是减法,和上面的过程类似。例如1-2*3。preOperand = 3,val = -1。计算:-1-(-2)+(-2)*3=-5。

如果上一步是减法。例如543。preOperand = 5x4=20,val = 20。计算:20-20+20*3 = 60。也就是说上一步乘法的操作数preOperand = 5x4=20。这样公式就统一了。

至此解答完毕。

class Solution {
    private String num;
    private int target;
    private List<String> result;
    public List<String> addOperators(String num, int target) {
        this.num = num;
        this.target  = target;
        result = new ArrayList<String>();
        dfs(0,"",0,0);
        return result;
    }
    
    private void dfs(int start,String expr,long value,long preOperand){
        if(start == num.length()){
            //System.out.println(expr+" "+value);
            if(value == target){
                result.add(expr);
            }
            return;
        }
        for(int  i = start ;i<num.length();i++){
            String t = num.substring(start,i+1);
            if(t.charAt(0)=='0' && i>start) break;
            long n = Long.parseLong(t);
            if(n > Integer.MAX_VALUE) break;
            if(start == 0){
                dfs(i+1,t,n,n);
            }else{
                dfs(i+1,expr+"+"+t,value+n,n);
                dfs(i+1,expr+"-"+t,value-n,-n);
                dfs(i+1,expr+"*"+t,value-preOperand+preOperand*n,preOperand*n);
            }
            
        }
    }
}

时间复杂度

在字符串的两个数字之间有4种操作。n个字符串有n-1个空格,所以时间复杂度是O(4n1)O(4^{n-1})

进一步优化

在计算 表达式expr,每次有字符串相加操作。可以使用StringBuilder。可以加快速度。链接