发表于

分治法

分治(divide-conquer)，将原问题分解为容易求解的子问题，再对子问题合并，实现对原问题求解。

自上而下分治+记忆化搜索

自下而上（动态规划）

241. 为运算表达式设计优先级

方法一：记忆化搜索
class Solution {
public:
    vector<int> operand;
    vector<char> ops;
    vector<int> diffWaysToCompute(string expression) {
        int n=expression.size();
        int i=0;
        while(i<n){
            if(isdigit(expression[i])){
                int val=0;
                while(i<n&&isdigit(expression[i])){
                    val=val*10+expression[i]-'0';
                    i++;
                }
                operand.push_back(val);
                // cout<<val<<endl;
            }else{
                ops.push_back(expression[i]);
                // cout<<expression[i]<<endl;
                i++;
            }
        }
        vector<vector<vector<int>>> dp(operand.size(),vector<vector<int>>(operand.size()));
        return backtrack(dp,0,dp.size()-1);
    }

    vector<int> backtrack(vector<vector<vector<int>>> &dp,int l,int r){
        if(l==r){
            return {operand[l]};
        }

        if(!dp[l][r].empty())
            return dp[l][r];

        for(int i=l;i<r;i++){
            auto left=backtrack(dp,l,i);
            auto right=backtrack(dp,i+1,r);
            for(int l_val:left){
                for(int r_val:right){
                    if(ops[i]=='+') dp[l][r].push_back(l_val+r_val);
                    else if(ops[i]=='-') dp[l][r].push_back(l_val-r_val);
                    else    dp[l][r].push_back(l_val*r_val);
                }
            }
        }
        return dp[l][r];
    }
};

932. 漂亮数组

对于一个正整数 N, 我们将其等分为两部分，left 和 right， 如果 left 部分是漂亮数组，right 部分也是漂亮数组， 同时 left 部分全部是奇数，right 部分全部是偶数，那么此时 left+right 组成的数组一定也是一个漂亮数组。

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans(n,1);
        divide(ans,0,n-1);
        return ans;
    }

    void divide(vector<int>& ans,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        divide(ans,left,mid);
        divide(ans,mid+1,right);
        for(int i=left;i<=mid;i++)
            ans[i]=ans[i]*2-1;
        for(int i=mid+1;i<=right;i++)
            ans[i]=2*ans[i];
    }
};

1763. 最长的美好子字符串

tag：切割出符合条件的子串，判断出现的大小写字符集

class Solution {
public:
    int maxLen=0,pos=-1;
    string longestNiceSubstring(string s) {
        int n=s.size();
        check(s,0,n-1);
        return maxLen==0?"":s.substr(pos,maxLen);
    }

    void check(string &s,int left,int right){
        if(left>=right)
            return;

        int lower=0,upper=0;
        for(int i=left;i<=right;i++){
            if(islower(s[i])){
                lower|=(1<<s[i]-'a');
            }else{
                upper|=(1<<s[i]-'A');
            }
        }
        // 大写字符集和小写字符集一样
        if(lower==upper){
            int len=right-left+1;
            if(len>maxLen){
                pos=left;
                maxLen=len;
            }
            // 从左到右分割，不需要下面的  
            // else if(len==maxLen&&left<pos){
            //     pos=left;
            // }
            return;
        }
        int valid=upper&lower;
        //大写字符集和小写字符集不一样，需要分割，没有成对出现时，valid相应位置为0
        int beg=left,end=left;
        while(end<=right){
            while(end<=right&&(valid&(1<<(tolower(s[end])-'a'))))
                end++;
            // cout<<left<<" "<<right<<" "<<beg<<" "<<end<<endl;
            check(s,beg,end-1);
            beg=end+1;
            end++;
        }

    }
};

395. 至少有 K 个重复字符的最长子串

class Solution {
public:
    int ans=0;
    int longestSubstring(string s, int k) {
        int n=s.size();
        check(s,0,n,k);
        return ans;
    }

    void check(string &s,int left,int right,int &k){
        if(left>=right)
            return;
        unordered_map<char,int> cnt;
        for(int i=left;i<right;i++){
            cnt[s[i]]++;
        }

        bool flag=true;
        int beg=left;
        for(int end=left;end<right;end++){
            if(cnt[s[end]]<k){
                flag=false;
                // cout<<beg<<" "<<end<<endl;
                check(s,beg,end,k);
                beg=end+1;
            }
        }

        if(flag)
            ans=max(ans,right-left);
        else
            check(s,beg,right,k);
      
    }
};