LeetCode:282. Expression Add Operators

这题第一反应还是使用回溯法，相当于把所有情况全部列举出来，但是做的时候有许多细节需要注意。

直接看代码：

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        backtrack(res, num, target, 0, 0, "", 0, '#');
        return res;
    }
private:
    void backtrack(vector<string> &res, const string &num, const int &target, long long val, int index, string exp, const long long pv, const char op) {
        if (index >= num.size() && val == target) {
            res.push_back(exp);
            return;
        }
        for (int l = 1; index + l <= num.size(); ++l) {
            string thisVal = num.substr(index, l);
            long long thisNum = stol(thisVal);
            if (to_string(thisNum).size() != thisVal.size()) continue;
            if (index == 0) 
                backtrack(res, num, target, val+thisNum, index+l, exp+thisVal, thisNum, '#');
            else {
                backtrack(res, num, target, val+thisNum, index+l, exp+"+"+thisVal, thisNum, '+');
                backtrack(res, num, target, val-thisNum, index+l, exp+"-"+thisVal, thisNum, '-');
                backtrack(res, num, target, (op == '-')? val+pv-pv*thisNum : (op == '+')? val-pv+pv*thisNum : val*thisNum, index+l, exp+"*"+thisVal, pv*thisNum, op);//很多细节
            }
        }
    }
};

有这么几点需要注意：
1.关于stol函数：很方便，可以直接将string转化为long，第一次使用
2.关于数字开头为0的解决方法：这个问题应该是经常会遇到的，这里的解决方法是

if (to_string(thisNum).size() != thisVal.size()) continue;

将string转化为数字之后再转化为string，看看string大小是否与之前还相等。如果不等，说明数字的开头有0被省略了。确实是个很巧妙的方法，以后可以使用，当然也可以直接检测string的首字母是否为’0’。
当然，相比于如何解决，更重要的是知道在什么场合下需要注意这个问题，依我看来，在string和数字相互转换的场合下，需要注意首字母为0的问题。
3.相对于这一题很重要的一点：如果我们不特殊处理一下乘法引起的计算顺序改变的问题，会将2+3*2计算为(2+3)*2。我一开始就中招了，下面是我一开始的代码：

class Solution {//！！！这个代码是错误的
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        backtrack(res, num, target, 0, 0, "");
        return res;
    }
private:
    void backtrack(vector<string> &res, const string &num, const int &target, long long val, int index, string exp) {
        if (index >= num.size() && val == target) {
            res.push_back(exp);
            return;
        }
        for (int l = 1; index + l <= num.size(); ++l) {
            string thisVal = num.substr(index, l);
            long long thisNum = stol(thisVal);
            cout << "val:" << val << " thisNum: " << thisNum << endl;
            if (index == 0) 
                backtrack(res, num, target, val+thisNum, index+l, exp+thisVal);
            else {
                backtrack(res, num, target, val+thisNum, index+l, exp+"+"+thisVal);
                backtrack(res, num, target, val-thisNum, index+l, exp+"-"+thisVal);
                backtrack(res, num, target, val*thisNum, index+l, exp+"*"+thisVal);
            }
        }
    }
};

所以我们需要记录一下之前的操作数和操作符，就像第一段代码那样，在乘法时做特殊处理。

LeetCode:282. Expression Add Operators

相关推荐