C/C++教程

算法39 leetcode22. 括号生成

本文主要是介绍算法39 leetcode22. 括号生成,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

开始的想法

生成n个独立的(),然后把最后一个往前面扔(重复这个过程)
但是不好实现

答案解法思路是类似生成然后去除不符合的项

用动规好理解一些

n+1可以理解为比n项多了一个括号,所以把n项放在括号里面p项和外面q项排列;p和q就转化成了子问题。但是要注意p和q的顺序是固定的,可以是p(q)、(p)q,但是为了保持不对称来避免重复项不能是pq()、()pq

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> brc;
        brc.push_back({""});
        brc.push_back({"()"});
        for(int i=2;i<=n;i++){
            vector<string> t;
            //利用n-1组合拼出n

            for(int a=0;a<i;a++){//a+b=n-1(p+q=n-1)
                int b=i-1-a;
                vector<string> p(brc[a]);
                vector<string> q(brc[b]);
                for( auto ps:p){
                    for( auto qs:q){
                        string ss="(";
                        ss=ss+ps+")"+qs;//(p)+q
                        t.emplace_back(ss);
                    }   
                }
            }
            brc.push_back(t);
        }
        return brc[n];    
    }
    
};
这篇关于算法39 leetcode22. 括号生成的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!