Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

题目链接

22. Generate Parentheses

看到这个题目，马上想到了剑指offer上做过的一道题，12个高矮不同的人。

坏消息是我已经忘掉那个题目是怎么做的了，只记得用位运算，各种骚操作转化成01组合做出来，

12个高矮不同的人

问题描述:

12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.

问题分析:

我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.

比如000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11

010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11

与Leetcode上的题目思路很类似，将010101组合转化成( ) 即可

如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个.

这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的

最为关键的一步是：

int bit_cnt(int n)
{
    int result = 0;
    //n&(n-1)作用：将n的二进制表示中的最低位为1的改为0
    for (; n; n &= n - 1, ++result);
    return result;
}

可以计算出对应个数的1，及其对应的值。

代码

#include <iostream>  
using namespace std;

int bit_cnt(int n)
{
    int result = 0;
    //n&(n-1)作用：将n的二进制表示中的最低位为1的改为0
    for (; n; n &= n - 1, ++result);
    return result;
}

int main(void)
{
    int F[3], B[3];//前排、后排
    int i, j, k, state, ok, ans = 0;
    for (state = 0; state < (1 << 6); ++state)
    {
        if (bit_cnt(state) == 3)//有3个1
        {
            i = j = 0;
            for (int k = 0; k < 6; ++k)
            {
                if (state&(1 << k))//第K位是不是1
                    F[i++] = k;
                else
                    B[j++] = k;
            }
            ok = 1;
            for (k = 0; k < 3; ++k)
            {
                if (B[k] < F[k])//后排比前排小，跳出
                {
                    ok = 0;
                    break;
                }
            }
            if (ok == 1) {
                cout << state << endl;
                cout << F[0] << " " << F[1] << " " << F[2] << " " << endl;
                cout << B[0] << " " << B[1] << " " << B[2] << " " << endl;
                cout << endl;
            }
            ans += ok;
        }
    }
    cout << ans << endl;
    return 0;
}

回到本题

问题描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

代码

class Solution {
public:
    int bit_cnt(int n)
    {
        int result = 0;
        //n&(n-1)作用：将n的二进制表示中的最低位为1的改为0
        for (; n; n &= n - 1, ++result);
        return result;
    }

    vector<string> generateParenthesis(int n) {
        int f, b, k, state, ans = 0;
        vector<string> answer;
        for (state = 0; state < (1 << n * 2); ++state) {
            if (bit_cnt(state) == n) {
                string res = "";
                f = 0, b = 0;//front,back 前后括号都是0个
                for (k = 0; k < n * 2; k++) {
                    if (state&(1 << k)) {//如果第k位是1
                        res += '(';
                        f++;
                    }
                    else {
                        res += ')';
                        b++;
                    }
                    if (f < b) break;
                }
                if (res.size() == n * 2) answer.push_back(res);
            }
        }
        return answer;
    }
};

大体上的思路都是一回事，这种递归嘛，应该也算不上。

也许就是骚操作吧

本文由 mmmwhy 创作，最后编辑时间为: May 2, 2019 at 01:48 pm

022. Generate Parentheses