022. Generate Parentheses

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

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

也许就是骚操作吧