存档

文章标签 ‘DFS’

查找字典中某个公共前缀的所有单词

2013年3月14日 2 条评论

---

练手,求给定公共前缀的所有单词集合,使用trie树,找到公共前缀后,DFS深搜即可。在Trie树节点中增加一个记录以当前串为前缀的单词个数,可以直接返回公共前缀单词个数。在Trie树类中增加一个存储公共前缀单词的集合指针,存储所求单词集合。

阅读全文...

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

2013年3月6日 15 条评论

---

给定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);
}

阅读全文...

微策略笔试题一道:数字序列和为0

2013年3月5日 10 条评论

---

这道深搜的题目写的我心情好别扭,代码也感觉别扭。希望路过的爱动手的牛牛们指导,不管是代码还是思路方面的建议都行;/握手

题目:序列123...N,N介于3和9之间,在其中加入+、-或者空格,使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问,如何获得所有组合?

我代码的思路就是深搜,处理空格时复杂一些,具体参数见注释。

阅读全文...

百度面试题:POJ 2192 - Zipper

2012年9月30日 8 条评论

---

百度二面的时候有一道题目没有答上来,回来一查,原来是POJ上的原题,是一个DP问题,当时有向这方面想,但始终没有找出重叠子问题,网上看到别人定义的子问题,感觉真心简单,关键看是否能找出子问题了,这个积累不是一时半日的,自己还是太菜。刚刚到POJ上AC了这道题,附题目链接:

POJ 2192: http://poj.org/problem?id=2192

题意:就是给定三个字符串A,B,C;判断C能否由AB中的字符组成,同时这个组合后的字符顺序必须是A,B中原来的顺序,不能逆序;例如:A:mnl,B:xyz;如果C为mnxylz,就符合题意;如果C为mxnzly,就不符合题意,原因是z与y顺序不是B中顺序。

DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;

有了这个定义,我们就可以找出状态转移方程了,初始状态dp[0][0] = 1:

dp[i][j] = 1 如果 dp[i-1][j] == 1 && C[i+j-1] == A[i-1]
dp[i][j] = 1 如果 dp[i][j-1] == 1 && C[i+j-1] == B[j-1]

代码如下:

阅读全文...