Given n pairs of parentheses, write a function to generate all combinations of well-formed 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 创作，最后编辑时间为: Jun 7, 2018 at 03:04 pm