首页 > 笔试面试题, 算法 数据结构 > 小米面试题一道:N对括号所有的合法状态

小米面试题一道:N对括号所有的合法状态

2013年3月6日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

给定N对括号,输出其所有的合法的组合状态,例如,N=3,所有的合法状态为:"((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路:还是深搜DFS的思路,深搜的过程关键在于记录已经用掉的左括号个数和右括号的个数,当用过的左括号个数小于右括号则非法;当二者个数和大于2N则非法;当二者个数相等且数目等于2N则为合法。

代码如下:

#include<iostream>
using namespace std;

#define PAIR 50

char str[PAIR * 2 + 1]; // 设括号对数不超过50, str记录括号组合状态

void DFS_bracket(int n, int left_used, int right_used)
{
	if(left_used == right_used && left_used + right_used == 2*n)
	{
		printf("%s\n",str);
		return;
	}
	if(left_used < right_used || left_used + right_used >= 2*n)
	{
		return ;
	}
	int index = left_used + right_used;
	str[index] = '(';
	DFS_bracket(n, left_used + 1, right_used);

	str[index] = ')';
	DFS_bracket(n, left_used, right_used + 1);
}

void main()
{
	int N;
	scanf("%d", &N);
	DFS_bracket(N,0,0);
}

(全文完)

  • armtt

    你的签名和我一样,有缘啊,哈哈,这个面试题最近考了,交个朋友吧,QQ号:452019937

    • Yx.Ac

      哈,是么~~是面的小米么~那我岂不是泄露我司题目了,,囧 我Q:568879319

  • TLinger

    组合数学中卡特兰数的一种应用Cn=C(2n n) - C(2n n+1),2n个符号('('')')任意排列有C(2n n)种可能,但对于合法状态而言,需要剔除排列中存在某一点处')'数目大于'('数目的情况,例如"(())()')'(()",这种情况有C(2n n+1)种。更详细的说明请谷歌“卡特兰数”。
    BTW,博客很棒。

    • Yx.Ac

      哈,是卡特兰数~~话说这方面有一系列的东东 :-) ,谢谢,多交流

  • http://likecer.com/ Likecer

    说错了……我当时是,搜索构建空间树,然后用栈来判断,虽然好理解,不过效率不高。所以组合数学和DP都是更好的方法@Likecer

    • Yx.Ac

      @Likecer 组合数学和DP分别如何做?我觉得递归的搜索+剪枝就挺方便 :-)

      • http://likecer.com Likecer

        时隔两年, 我来回一个: Catanlan数列或者区间DP显然可做.

        • Yx.Ac

          :-)

  • http://likecer.com/ Likecer

    栈是最简单的方法~

  • lovey

    这个动态规划可以解决的吧

  • Wayne

    幸哥,“当用过的左括号个数大于右括号则非法”是不是应该改为“当用过的左括号个数小于右括号则非法”?

    • Yx.Ac

      @Wayne good,3ks,你怎么有时间看这个了,dt?

  • creepyuncle

    这题不用dfs吧。组合数学问题。。可直接得解