首页 > 代码库 > 【编程题目】四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
【编程题目】四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
46.搜狐（运算）：
四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
跟12个人排高矮的题目差不多。 用 0 表示 “（”，用 1 表示“）” 则需要数字二进制最低8位有 4个1和 4个0，且从低位到高位对1 和 0 计数时，0 出现的次数不能超过 1 出现的次数。
/*46.搜狐（运算）：四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））*/#include <stdio.h>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=http://www.mamicode.com/1，num0=父节点num0;num1=父节点num1+1;右孩子data=0，num0=父节点num0+1,num1=父节点num1;
如何num1=num0,只增加一个左孩子1，同时新增加的节点入队列
（3）重复步骤（2）知道队列为空
（4）统计叶子节点的个数即是结果
我没仔细看，因为没给代码。
http://blog.csdn.net/lihappy999/article/details/7395943 中有通用的方法 用递归实现 完全搜索后判定 验证通过
#include<iostream>#include<cassert>#include <vector>using namespace std ;void Print(vector<char> v){ for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg) cout<<*beg<<" "; cout<<endl;}void MatchNums(int nSize,int nLen,vector<char> &v){ int nLeftBrackets=0; int nRightBrackets=0; for (vector<char>::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 <char> v; int n=6; MatchNums(n,n,v); return 1;}