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

时间:2022-05-24 15:52:07

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