w***g 发帖数: 5958 | 1 去年面Google的时候被问的。
1.给出一个字符串,全都由(和)组成。写个程序判断括号是否嵌套正确。
如()(())是正确的,)()(是不正确的。
2.给出一个偶数n,写一个程序产生所有长度为n的嵌套正确的括号串。
2有点像全排列的问题。我当时只想到了用到指数空间的算法,比较简洁。谁来给个常数
空间比较简洁的算法吧。 |
p*****2 发帖数: 21240 | 2
常数
第一题是常规题。第二题是从N里边选N/2个‘(’, 的组合,然后再用第一题来判断
就可以了吧?
【在 w***g 的大作中提到】 : 去年面Google的时候被问的。 : 1.给出一个字符串,全都由(和)组成。写个程序判断括号是否嵌套正确。 : 如()(())是正确的,)()(是不正确的。 : 2.给出一个偶数n,写一个程序产生所有长度为n的嵌套正确的括号串。 : 2有点像全排列的问题。我当时只想到了用到指数空间的算法,比较简洁。谁来给个常数 : 空间比较简洁的算法吧。
|
i******r 发帖数: 793 | |
p*****2 发帖数: 21240 | 4
还真是。我还想着用stack呢。
【在 i******r 的大作中提到】 : 判断括号是否正确,就是一个计数
|
S*******w 发帖数: 24236 | 5 能展开说说吗
【在 p*****2 的大作中提到】 : : 还真是。我还想着用stack呢。
|
p*****2 发帖数: 21240 | 6
见到‘(’ +1, 见到‘)’ -1呀。
最后应该是counter==0 就对。
如果最后counter!=0 或者 counter==0 下一个是')' 就error out.
【在 S*******w 的大作中提到】 : 能展开说说吗
|
p*****2 发帖数: 21240 | 7
static bool Check(string input)
{
int counter = 0;
int i = 0;
while (i < input.Length)
{
if (input[i] == '(')
counter++;
if (input[i] == ')')
if (counter == 0)
return false;
else
counter--;
i++;
}
return counter == 0;
}
【在 S*******w 的大作中提到】 : 能展开说说吗
|
a********m 发帖数: 15480 | 8 1直接扫描就可以了吧?(->1, )->-1, 只要最后结果是0而且任何时候结果大于(或者
等于,问清楚要求)就是有效的。 |
p*****2 发帖数: 21240 | 9
第二题有好的idea吗?
【在 a********m 的大作中提到】 : 1直接扫描就可以了吧?(->1, )->-1, 只要最后结果是0而且任何时候结果大于(或者 : 等于,问清楚要求)就是有效的。
|
B******5 发帖数: 4676 | 10 BFS行不?
【在 p*****2 的大作中提到】 : : 第二题有好的idea吗?
|
|
|
p*****2 发帖数: 21240 | 11
具体谈谈?
【在 B******5 的大作中提到】 : BFS行不?
|
H***e 发帖数: 476 | 12 第二题其实也一样吧
假想有一个这样的tree,每次在一个node expand, 只有两种情况 (或者 )。
秋虫说的那个数字作为值传,
然后分别看如果expand (和), 值还满足条件不,满足则expand.
也就是backtracking了。
到最后长度为N则打印。
【在 p*****2 的大作中提到】 : : 具体谈谈?
|
S*******w 发帖数: 24236 | 13 see thanks!
【在 p*****2 的大作中提到】 : : 具体谈谈?
|
i**********e 发帖数: 1145 | 14 第二题就基本dfs吧,空间肯定不可能常数(如果stack space也算空间的话)。为什么
呢?
因为所有长度为n的嵌套正确的括号串的总数就是第 n/2 个 catalan number 。
给个例子,n=6 的时候,需要打印的总数是第 3 个 catalan number = C3 = 5.
当 n = 30, 需要打印的个数是 C15 = 9694845 个。
所以空间耗费肯定不可能常数。DFS 递归程序不是 tail-recursive,所以转换成非递
归不是那么直接。如果硬要转换的话,那也得用stack来模拟DFS,也是一样要耗空间。
最直接的程序(也应该是最简洁的)就是数,‘(’+1,‘)’就 -1,任何时候 < 0
就停止递归。
利用 n = 30 代入函数,
./a.out 14.87s user
可以做适当优化来剪枝(程序也没那么复杂),
./a.out 1.79s user |
B******5 发帖数: 4676 | 15 嗯,我就是这么想的,
DFS BFS都行,注意剪枝就好了
【在 H***e 的大作中提到】 : 第二题其实也一样吧 : 假想有一个这样的tree,每次在一个node expand, 只有两种情况 (或者 )。 : 秋虫说的那个数字作为值传, : 然后分别看如果expand (和), 值还满足条件不,满足则expand. : 也就是backtracking了。 : 到最后长度为N则打印。
|
H***e 发帖数: 476 | 16 public void printParenthesis(Stack path, int sum, int n){
if (sum<0 || path.size() > n){
return;
}
if(path.size() == n && sum == 0 ){
System.out.print(path.toString()+"\n");
return;
}
path.push('(');
printParenthesis(path, sum+1, n);
path.pop();
path.push(')');
printParenthesis(path, sum-1, n);
path.pop();
} |
p*****2 发帖数: 21240 | 17
我做了做要传两个值。
static void Find(StringBuilder sb, int n, int lcount,int rcount)
{
if (sb.Length == n)
{
Console.WriteLine(sb);
return;
}
if (lcount < n/2)
{
sb.Append('(');
Find(sb, n, lcount+1,rcount);
sb.Length--;
}
if (rcount
{
sb.Append(')');
Find(sb, n, lcount,rcount+1);
sb.Length--;
}
}
static void All(int n)
{
StringBuilder sb = new StringBuilder();
Find(sb, n, 0,0);
}
【在 H***e 的大作中提到】 : 第二题其实也一样吧 : 假想有一个这样的tree,每次在一个node expand, 只有两种情况 (或者 )。 : 秋虫说的那个数字作为值传, : 然后分别看如果expand (和), 值还满足条件不,满足则expand. : 也就是backtracking了。 : 到最后长度为N则打印。
|
i**********e 发帖数: 1145 | 18 恩,对的。这就是做了重要的剪枝,减少了很多不必要的递归。
程序写的不错,赞一下!
【在 p*****2 的大作中提到】 : : 我做了做要传两个值。 : static void Find(StringBuilder sb, int n, int lcount,int rcount) : { : if (sb.Length == n) : { : Console.WriteLine(sb); : return; : } : if (lcount < n/2)
|
p*****2 发帖数: 21240 | 19
多谢大牛。深感荣幸。一会儿还要好好体会体会你说的话。那个什么number也是第一次
见到。还得查查。
【在 i**********e 的大作中提到】 : 恩,对的。这就是做了重要的剪枝,减少了很多不必要的递归。 : 程序写的不错,赞一下!
|
w***g 发帖数: 5958 | 20 跟我老婆想的一样。你们都比我牛。
0
【在 i**********e 的大作中提到】 : 第二题就基本dfs吧,空间肯定不可能常数(如果stack space也算空间的话)。为什么 : 呢? : 因为所有长度为n的嵌套正确的括号串的总数就是第 n/2 个 catalan number 。 : 给个例子,n=6 的时候,需要打印的总数是第 3 个 catalan number = C3 = 5. : 当 n = 30, 需要打印的个数是 C15 = 9694845 个。 : 所以空间耗费肯定不可能常数。DFS 递归程序不是 tail-recursive,所以转换成非递 : 归不是那么直接。如果硬要转换的话,那也得用stack来模拟DFS,也是一样要耗空间。 : 最直接的程序(也应该是最简洁的)就是数,‘(’+1,‘)’就 -1,任何时候 < 0 : 就停止递归。 : 利用 n = 30 代入函数,
|
p*****2 发帖数: 21240 | 21
你当时怎么答的?
【在 w***g 的大作中提到】 : 跟我老婆想的一样。你们都比我牛。 : : 0
|
q****x 发帖数: 7404 | 22 special case of next_permutation, O(n) space, which is minimum as you need O
(n) to store the solution.
常数
【在 w***g 的大作中提到】 : 去年面Google的时候被问的。 : 1.给出一个字符串,全都由(和)组成。写个程序判断括号是否嵌套正确。 : 如()(())是正确的,)()(是不正确的。 : 2.给出一个偶数n,写一个程序产生所有长度为n的嵌套正确的括号串。 : 2有点像全排列的问题。我当时只想到了用到指数空间的算法,比较简洁。谁来给个常数 : 空间比较简洁的算法吧。
|