[leetcode]分治算法之Different Ways to Add Parenthese

╰+哭是因爲堅強的太久メ 2021-09-28 12:08 257阅读 0赞

### 分治算法之Different Ways to Add Parentheses ###

*  分治的思考
 *  其他的学习
 *  题干
 *  答案

# 分治的思考 #

分治：把问题分为k份，然后再将这k份连起来。

方法：一般用递归来做。

注意：处理递归终止条件，即问题规模最小的情况

典型例题：归并排序、快速排序

# 其他的学习 #

string.substr(pos,len) 的用法

# 题干 #

[leetcode入口][leetcode]

# 答案 #

很慢的一种答案，但是毕竟是自己想出来的。

先把数字和字符作为int从字符分离出来，存到一个`vector<int>`里面，注意运算符存的是位置

然后用递归对返回的`vector<int>`中的数字两两组合

class Solution { 
    public:
        vector<int> diffWaysToCompute(string input) { 
            
            vector<int> res;
            vector<int> v; //存储字符和数字
            
            res.clear();
            v.clear();
            
            string a="";
            for(int i=0;i<input.size();i++){ 
                
                if(input[i]!='+' && input[i]!='-' && input[i]!='*'){ 
                    a+=input[i];    
                }
                else{ 
                    v.push_back(stoi(a));
                    a="";
                    v.push_back(i); //把位置加进去
                }
            }
            
            v.push_back(stoi(a));
            if(v.size()==1) return v;
            
            for(int i=1;i<v.size();i=i+2){ 
                int index=v[i];
                char op=input[index];
                
                vector<int> left=diffWaysToCompute(input.substr(0,index));
                vector<int> right=diffWaysToCompute(input.substr(index+1));
                
                if(op=='+'){ 
                    for(int i=0;i<left.size();i++){ 
                        for(int j=0;j<right.size();j++){ 
                            res.push_back(left[i]+right[j]);
                        }
                    }
                }
                else if(op=='-'){ 
                    for(int i=0;i<left.size();i++){ 
                        for(int j=0;j<right.size();j++){ 
                            res.push_back(left[i]-right[j]);
                        }
                    }
                }
                else{ 
                    for(int i=0;i<left.size();i++){ 
                        for(int j=0;j<right.size();j++){ 
                            res.push_back(left[i]*right[j]);
                        }
                    }
                }
            }
            
            return res;
        }
    };

改进（网上代码）：

class Solution { 
    public:
        vector<int> diffWaysToCompute(string input) { 
            vector<int> res;
            for (int i = 0; i < input.size(); ++i) { 
                if (input[i] == '+' || input[i] == '-' || input[i] == '*') { 
                    vector<int> left = diffWaysToCompute(input.substr(0, i));
                    vector<int> right = diffWaysToCompute(input.substr(i + 1));
                    for (int j = 0; j < left.size(); ++j) { 
                        for (int k = 0; k < right.size(); ++k) { 
                            if (input[i] == '+') res.push_back(left[j] + right[k]);
                            else if (input[i] == '-') res.push_back(left[j] - right[k]);
                            else res.push_back(left[j] * right[k]);
                        }
                    }
                }
            }
            if (res.empty()) res.push_back(stoi(input));
            return res;
        }
    };

[leetcode]: https://leetcode.com/problems/different-ways-to-add-parentheses/