题意

给定数字字符串ABCDEFG..., 判断A+B+C+D+E+F+G...,A-B-C-D-E-F-G...,A*B*C*D*E*F*G... 三个值中,是否存在等于target的值的

限制:

字符串长度不超过10

方法

分别记录字符串和运算结果,分别计算

对于加法,减法,和乘法,分别处理

每次处理,用一个变量记录字符串,一个变量记录结果值.

最后比较结果值和目标值是否一致,如果一致则满足题意.

以题目样例数据"123",6为例

最后输出即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串vector
     */
    vector<string> addOpt(string num, int target) {
        vector<string> ans;
        string s = num.substr(0,1); // 加法字符串
        int v = num[0]-'0'; // 加法结果
        for(int i = 1;i<num.length();i++){
            v+=num[i]-'0';
            s+="+"+num.substr(i,1);
        }
        if(v == target)ans.push_back(s); // 对比结果
        
        s = num.substr(0,1); // 乘法字符串
        v = num[0]-'0'; // 乘法结果
        for(int i = 1;i<num.length();i++){
            v*=num[i]-'0';
            s+="*"+num.substr(i,1);
        }
        if(v == target)ans.push_back(s);  // 对比结果
        
        s = num.substr(0,1); // 减法字符串
        v = num[0]-'0'; // 减法结果
        for(int i = 1;i<num.length();i++){
            v-=num[i]-'0';
            s+="-"+num.substr(i,1);
        }
        if(v == target)ans.push_back(s); // 对比结果
        
        return ans;
    }
};

复杂度分析

时间复杂度: 主要是原始字符串中加入了符号进行计算,所以和原始字符串长度相关,所以时间复杂度为$O(n)O(n)$

空间复杂度: 新的字符串只是原始字符串数字两两之间插入了符号,所以空间复杂度为$O(n)O(n)$

基于函数指针和配表的代码优化

注意到上面我们对 加法 减法 乘法 分别做了三次处理.

而这三次处理中,只有字符串中的运算符,和运算的函数不同,其余部分都是相同的.

所以我们可以把这个字符和运算抽离到一个列表里.

再用循环,每次按照配的列表处理.

这样就省去 5行/7行 的重复一样的代码

如果未来还要加异或,与运算的话,只需要改动配置表即可.

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串vector
     */
    vector<string> addOpt(string num, int target) {
        vector<string> ans;
        for(auto [opstr,fn]: vector<pair<string,function<int(int,int)> > > {
            {"+", [] (int x, int y) { return x + y; }},
            {"-", [] (int x, int y) { return x - y; }},
            {"*", [] (int x, int y) { return x * y; }},
        }){
            string s = num.substr(0,1); // 运算字符串
            int v = num[0]-'0'; // 运算结果
            for(int i = 1;i<num.length();i++){
                v = fn(v,num[i]-'0');
                s+= opstr + num.substr(i,1);
            }
            if(v == target)ans.push_back(s); // 满足则增加字符串
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 主要是代码书写上的减少重复,所以时间复杂度也是$O(n)O(n)$

空间复杂度: 新的字符串只是原始字符串数字两两之间插入了符号,所以空间复杂度为$O(n)O(n)$