46.搜狐（运算）：

四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

 

跟12个人排高矮的题目差不多。 用 0 表示 “（”，用 1 表示“）” 则需要数字二进制最低8位有 4个1和 4个0，且从低位到高位对1 和 0 计数时，0 出现的次数不能超过 1 出现的次数。

/*46.搜狐（运算）：四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））*/#include 
     
      int c_bits(int n){    int result = 0;    for(; n; n &= n-1, result++);    return result;}int main(){    int i;    int ways = 0;    //0代表"（" 1代表 "）" 0必须在1前面    for (i = 0; i < (1<<7); i++)    {        if (c_bits(i) == 4)        {            int one_n = 0;            int zero_n = 0;            for (int j = 0; j < 8; j++)            {                if (((i >> j) & 1) == 0)                {                    zero_n += 1;                }                else                {                    one_n += 1;                }                if (zero_n > one_n)                {                    break;                }            }            if (one_n == 4 && zero_n == 4)            {                ways++;                printf("way %d:", ways);                for (int j = 7; j >= 0; j--)                {                    if (((i >> j) & 1) == 0)                    {                        printf("( ");                    }                    else                    {                        printf(") ");                    }                }                printf("\n");            }        }    }    return 0;}
     

网上有一种方法与我的差不多，区别在判断是否符合要求时 ：

http://www.cnblogs.com/GoAhead/archive/2012/05/30/2525824.html

把所有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）统计叶子节点的个数即是结果

我没仔细看，因为没给代码。

 

 中有通用的方法 用递归实现 完全搜索后判定 验证通过

#include
     
      #include
      
       #include 
       
        using namespace std ;void Print(vector
        
          v){    for (vector
         
          ::iterator beg=v.begin();beg!=v.end();++beg)        cout<<*beg<<" ";    cout<
          
            &v){ int nLeftBrackets=0; int nRightBrackets=0; for (vector
           
            ::iterator beg=v.begin();beg!=v.end();++beg) { if(*beg=='(') nLeftBrackets++; else nRightBrackets++; if(nRightBrackets>nLeftBrackets) return; if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets) Print(v); } if (nLen>0) { v.push_back('('); MatchNums(nSize,nLen-1,v); v.pop_back(); v.push_back(')'); MatchNums(nSize,nLen-1,v); v.pop_back(); }}int main(){ vector 
            
              v; int n=6; MatchNums(n,n,v); return 1;}