四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

时间:2021-06-02 19:27:48

该题的公式版暂时还没弄出来,感觉是应该可以按照排列组合弄出来的。下面给出程序版的

第一种思想:

把所有8位以内的二进制数循环一次,对于每一个二进制数的每一位,从高到低依次相加,其中遇到0的话加-1,遇到1加1,每次加的结果需要大于等于0

加完所有位的结果应该为0,满足两个条件的即是一种组合

第二种思想:

我们可以用生成二叉树的方法解决,重新定义一个数据结构,数据结构如下:

struct Node{

        int data;//0或1

        int num0;//0出现的次数

        int num1;//1出现的次数

        struct Node* lchild;

        struct Node* rchild;

};

同时我们需要用一个队列保存叶子节点的指针,目的是为了降低时间复杂度

步骤如下:

(1)用元素1生成根节点,同时num1++,num0=0,lchild=NULL,rchld=null;把该节点入队列

(2)从队列取队首元素,比较num1和num0的大小,当num1=4的时候节点不再增加;如果num1大于num0,则为该节点生成生成左右孩子,左孩子data=1,num0=父节点num0;num1=父节点num1+1;右孩子data=0,num0=父节点num0+1,num1=父节点num1;

如何num1=num0,只增加一个左孩子1,同时新增加的节点入队列

(3)重复步骤(2)知道队列为空

(4)统计叶子节点的个数即是结果