LeetCode 282. 给表达式添加运算符

àì夳堔傛蜴生んèń 2022-10-29 07:36 2阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方写法][Link 1]

//解法一：官方解法
    class Solution {
        
    
      public ArrayList<String> answer;
      public String digits;
      public long target;
    
      public void recurse(
          int index, long previousOperand, long currentOperand, long value, ArrayList<String> ops) {
        
        String nums = this.digits;
    
        // Done processing all the digits in num
        if (index == nums.length()) {
        
    
          // If the final value == target expected AND
          // no operand is left unprocessed
          if (value == this.target && currentOperand == 0) {
        
            StringBuilder sb = new StringBuilder();
            ops.subList(1, ops.size()).forEach(v -> sb.append(v));
            this.answer.add(sb.toString());
          }
          return;
        }
    
        // Extending the current operand by one digit
        currentOperand = currentOperand * 10 + Character.getNumericValue(nums.charAt(index));
        String current_val_rep = Long.toString(currentOperand);
        int length = nums.length();
    
        // To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
        // valid operand. Hence this check
        if (currentOperand > 0) {
        
    
          // NO OP recursion
          recurse(index + 1, previousOperand, currentOperand, value, ops);
        }
    
        // ADDITION
        ops.add("+");
        ops.add(current_val_rep);
        recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.remove(ops.size() - 1);
        ops.remove(ops.size() - 1);
    
        if (ops.size() > 0) {
        
    
          // SUBTRACTION
          ops.add("-");
          ops.add(current_val_rep);
          recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
          ops.remove(ops.size() - 1);
          ops.remove(ops.size() - 1);
    
          // MULTIPLICATION
          ops.add("*");
          ops.add(current_val_rep);
          recurse(
              index + 1,
              currentOperand * previousOperand,
              0,
              value - previousOperand + (currentOperand * previousOperand),
              ops);
          ops.remove(ops.size() - 1);
          ops.remove(ops.size() - 1);
        }
      }
    
      public List<String> addOperators(String num, int target) {
        
    
        if (num.length() == 0) {
        
          return new ArrayList<String>();
        }
    
        this.target = target;
        this.digits = num;
        this.answer = new ArrayList<String>();
        this.recurse(0, 0, 0, 0, new ArrayList<String>());
        return this.answer;
      }
    }

[另一篇题解 用的StringBuilder操作][_StringBuilder]

//写法二：
    class Solution {
        
        public List<String> addOperators(String num, int target) {
        
        List<String> result = new ArrayList<>();
        addOperatorsHelper(num, target, result, new StringBuilder(), 0, 0, 0);
        return result;
    }
    
    private void addOperatorsHelper(String num, int target, List<String> result, StringBuilder path, int start, long eval, long pre) {
        
        if (start == num.length()) {
        
            if (target == eval) {
        
                result.add(path.toString());
            }
            return;
    
        }
        for (int i = start; i < num.length(); i++) {
        
            // 数字不能以 0 开头
            if (num.charAt(start) == '0' && i > start) {
        
                break;
            }
            long cur = Long.parseLong(num.substring(start, i + 1));
            int len = path.length();
            if (start == 0) {
        
                addOperatorsHelper(num, target, result, path.append(cur), i + 1, cur, cur);
                path.setLength(len);
            } else {
        
    
                // 加当前值
                addOperatorsHelper(num, target, result, path.append("+").append(cur), i + 1, eval + cur, cur);
                path.setLength(len);
                // 减当前值
                addOperatorsHelper(num, target, result, path.append("-").append(cur), i + 1, eval - cur, -cur);
                path.setLength(len);
                // 乘当前值
                addOperatorsHelper(num, target, result, path.append("*").append(cur), i + 1, eval - pre + pre * cur,
                                   pre * cur);
                path.setLength(len);
            }
        }
    }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/7e7b6f71e27344898d1a676ec13b71e4.png
[Link 1]: https://leetcode-cn.com/problems/expression-add-operators/solution/gei-biao-da-shi-tian-jia-yun-suan-fu-by-leetcode/
[_StringBuilder]: https://leetcode-cn.com/problems/expression-add-operators/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-52/