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有点像全排列的问题。我当时只想到了用到指数空间的算法，比较简洁。谁来给个常数
: 空间比较简洁的算法吧。
|
