LeetCode 282 给表达式添加运算符[回溯] HERODING的LeetCode之路

LeetCode 282 给表达式添加运算符[回溯] HERODING的LeetCode之路
解题思路:
一道从思路上不是很复杂的回溯题,但是细节拉满,值得注意。

  1. 首先在回溯中判断是否到达最后一个位置,到达了判断res是否为target,不是则return,是放到ans中;
  2. 遍历num,一位一位地前进,注意由于不能有前导零的存在,需要进行判断,即固定住头如果是0,那么不能往后遍历;
  3. 第三步记录下得到的新的数,然后进行加减乘运算;
  4. 最后for循环结束后回溯,将expr重置为0。

中间其实很多细节,包括传参由于参数过多,可以内置函数或者把参数作为类的属性,代码如下:

class Solution {
private:
    int n;
    int target;
    vector<string> ans;
    string num;
public:
    vector<string> addOperators(string num, int target) {
        n = num.length();
        this -> target = target;
        this -> num = num;
        string expr;
        backtrack(expr, 0, 0, 0);
        return ans;
    }
    void backtrack(string& expr, int i, long res, long mul) {
        if (i == n) {
            if (res == target) {
                ans.emplace_back(expr);
            }
            return;
        }
        int signIndex = expr.size();
        if (i > 0) {
            expr.push_back(0); // 占位,下面填充符号
        }
        long val = 0;
        // 枚举截取的数字长度(取多少位),注意数字可以是单个 0 但不能有前导零
        for (int j = i; j < n && (j == i || num[i] != '0'); ++j) {
            val = val * 10 + num[j] - '0';
            expr.push_back(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);
            }
        }
        expr.resize(signIndex);
    }
};



上一篇:家庭记账本app进度之下拉框和数字转轮的相关应用


下一篇:洛谷P1632 点的移动 题解 枚举