leetcode 282. Expression Add Operators 任意添加运算符计算结果 +深度优先遍历DFS

系统管理员 2022-06-08 14:20 119阅读 0赞

between the digits so they evaluate to the target value.

Examples:  
“123”, 6 -> \[“1+2+3”, “1\*2\*3”\]  
“232”, 8 -> \[“2\*3+2”, “2+3\*2”\]  
“105”, 5 -> \[“1\*0+5”,”10-5”\]  
“00”, 0 -> \[“0+0”, “0-0”, “0\*0”\]  
“3456237490”, 9191 -> \[\]

给定一个字符串，求给定的和（DFS+回溯）  
本题注意点  
1.取数字的时候可能 超过int的范围，用long来处理  
2.前导0  
3.乘法要记录上次的计算结果并减去  
需要这么几个变量，一个是记录上次的计算结果curRes，一个是记录上次被加或者被减的数preNum，一个是当前准备处理的数curNum。当下一轮搜索是加减法时，preNum就是简单换成curNum，当下一轮搜索是乘法时，preNum是preNum乘以curNum。

建议和[leetcode 95. Unique Binary Search Trees II 递归构造所有可能的搜索二叉树BST + 卡特兰数][leetcode 95. Unique Binary Search Trees II _BST _] 和 [leetcode 241. Different Ways to Add Parentheses 深度优先遍历DFS + 类似构造所有的二叉搜索树][leetcode 241. Different Ways to Add Parentheses _DFS _] 和 [leetcode 241. Different Ways to Add Parentheses 深度优先遍历DFS + 类似构造所有的二叉搜索树][leetcode 241. Different Ways to Add Parentheses _DFS _] 一起学习，因为做法感觉类似

嗯嗯，就是这么简单与难，所以呢？还得学习。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    
    /*
     * http://blog.csdn.net/mine_song/article/details/71024333
     * 这个需要记住，好好学习吧
     * 面对实习工作的压力，你还差很多
     * */
    class Solution 
    {
        public List<String> addOperators(String num, int target) 
        {
            List<String> res = new ArrayList<String>();
            if (num == null || num.length() == 0)
                return res;
            calaByIndexDFS(res, "", num, target, 0, 0, 0);
            return res;
        }
    
        /*
         * 这里使用long是考虑到int越界
         * */
        public void calaByIndexDFS(List<String> res, String calaStr, String num,
                int target, int pos, long curRes, long preRes) 
        {
            if(pos==num.length())
            {
                if(target==curRes)
                    res.add(calaStr);
            }else 
            {
                for(int i=pos;i<num.length();i++)
                {
                    // 得到当前截出的数
                    // 对于前导为0的数予以排除，pos为第一位
                    if(i!=pos && num.charAt(pos)=='0')
                        return ;
    
                    // 处理前导的另一种方法，当前substring长度和curNum长度不等说明有前导0
                    // 处理前导0的情况比如“105”，5一种结果是1*05
                    // if (num.substring(pos, i + 1).length() !=
                    // String.valueOf(curNum).length())
    
                    // return;
                    // 如果不是第一个字母时，可以加运算符，否则只加数字
                    long curNum=Long.parseLong(num.substring(pos, i+1));
                    if(pos==0)
                        calaByIndexDFS(res, calaStr+curNum, num, target, i+1, curNum, curNum);
                    else 
                    {
                        calaByIndexDFS(res, calaStr+"+"+curNum, num, 
                                target, i+1, curRes+curNum, curNum);
    
                        calaByIndexDFS(res, calaStr+"-"+curNum, num, 
                                target, i+1, curRes-curNum, -curNum);
    
                        // 注意乘法，因为之前加了preNum，本次要减去！
                        calaByIndexDFS(res, calaStr+"*"+curNum, num, 
                                target, i+1, curRes-preRes + preRes*curNum, preRes*curNum);
                    }
                }
            }
        }
    }

下面是C++的做法，这一道题十分值得学习，属于典型的DFS深度优先遍历的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        vector<string> res;
        vector<string> addOperators(string num, int target) 
        {
            if (num.length() <= 0)
                return res;
    
            dfs(num, target, 0, 0, 0, "");
            return res;
        }
    
        void dfs(string num,int target, int index, long now, long pre, string one)
        {
            if (index == num.length())
            {
                if (now == target)
                    res.push_back(one);
                return;
            }
            else
            {
                for (int i = index; i < num.length(); i++)
                {
                    if (i > index && num[index] == '0')
                        return;
                    else
                    {
                        long long a = stoll(num.substr(index, i - index + 1));
                        if (index == 0)
                            dfs(num, target, i + 1, a, a, to_string(a));
                        else
                        {
                            dfs(num, target, i + 1, now + a, a, one+"+"+to_string(a));
                            dfs(num, target, i + 1, now - a, -a, one+"-"+to_string(a));
                            dfs(num, target, i + 1, now-pre+pre*a, pre*a, one+"*"+to_string(a));
                        }
                    }
                }
            }
        }
    };

[leetcode 95. Unique Binary Search Trees II _BST _]: http://blog.csdn.net/jackzhang_123/article/details/77948273
[leetcode 241. Different Ways to Add Parentheses _DFS _]: http://blog.csdn.net/jackzhang_123/article/details/78092468