分治法

241. 为运算表达式设计优先级（经典分治法）

和归并排序的方法很相似。
将加括号的问题转化为，对于每个运算符号，先执行两端的表达式，然后在根据这个运算符进行运算。
两端的表达式的结果也不是唯一的，其中某一端的表达式的结果也是 多个像之前的分割操作的子集的和。
注意这里字符里面没有运算符的情况。然后就是这里的stoi也很重要，字符串转化为int类型。

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ways;
        for(int i = 0; i < expression.length(); i++){
            char c = expression[i];
            if(c == '+' || c == '-' || c == '*') {//以运算符为分割线前后都为括号！！！
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i+1));
                for(const int &  l : left){
                    for(const int & r : right){
                        switch(c) {
                            case '+' : ways.push_back(l + r); break;
                            case '-' : ways.push_back(l - r); break;
                            case '*' : ways.push_back(l * r); break;
                        }
                    }
                }
            }
        }
        if(ways.empty()) ways.push_back(stoi(expression));//如果当前没有运算符，那么就是完全由数字组成的。
        return ways;
    }
};

932. 漂亮数组（实在是难）

如果你有n的漂亮数组，想知道2n的漂亮数组，那么通过将n2-1作为前部（奇数），n2作为后半部分（偶数）。那么就能够的到2n的漂亮数组。

class Solution {
public:
    unordered_map<int,vector<int> > mp;
    vector<int> beautifulArray(int N) {
        return f(N);
    }
    vector<int> f(int N) {
        vector<int> ans(N, 0);
        int t = 0;
        if (mp.find(N) != mp.end()) {
            return mp[N];
        }
        if (N != 1) {
            for (auto x : f((N+1)/2)){
                ans[t++]= 2 * x - 1;
            } 
            for (auto x : f(N/2)){
                ans[t++] =  2 * x;
            }
        }else {
            ans[0] = 1;
        }
        mp[N] = ans;
        return ans;
    }
};