请教cracking the code interview两题# JobHunting - 待字闺中
g*o
1 楼
我是第5版书
（1）4.7题 求不带parent指针的binary tree的LCA(不考虑node不在tree里的情况）
书上的解法很罗嗦，很容易漏掉某种情况,leetcode的代码就简洁多了，如下：
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&
R subtrees
}
想确认下leetcode的代吗覆盖所有corner case了吗？ 至少我没看出什么问题。
(2)9.5题 Write a method to compute all permutations of a string
我觉得书上解法的复杂度比 o(n!)要大？
那些recursion和for loop就达到o(n!),而书上的解法用string相加，所有每次都要花o
(n)来做string insert，我怎么感觉总复杂度是o((n!)^2)
要我我就用下面这个做法了
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
（1）4.7题 求不带parent指针的binary tree的LCA(不考虑node不在tree里的情况）
书上的解法很罗嗦，很容易漏掉某种情况,leetcode的代码就简洁多了，如下：
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&
R subtrees
}
想确认下leetcode的代吗覆盖所有corner case了吗？ 至少我没看出什么问题。
(2)9.5题 Write a method to compute all permutations of a string
我觉得书上解法的复杂度比 o(n!)要大？
那些recursion和for loop就达到o(n!),而书上的解法用string相加，所有每次都要花o
(n)来做string insert，我怎么感觉总复杂度是o((n!)^2)
要我我就用下面这个做法了
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
