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

时间:2022-04-04 04:13:45

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=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;
}