g****o
发帖数: 547 | 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
}
}
} | p*****2
发帖数: 21240 | | g****o
发帖数: 547 | 3 感谢大牛回帖！
要不大家有空一起总结下书里算法的问题？
感觉书里的题目还是不错的。重考率很高
我on campus interview 80%的题书里都有
除了上面的两道，还被问了OOD的扑克牌设计
【在 p*****2 的大作中提到】
: 这本书问题很多。看看就算了。那个作者水平一般。
| p*****2
发帖数: 21240 | 4
我现在重点是system design了。CC150上的题目我总结过，而且很多题leetcode上也有
。CC150上的考到的概率确实很高。
【在 g****o 的大作中提到】
: 感谢大牛回帖！
: 要不大家有空一起总结下书里算法的问题？
: 感觉书里的题目还是不错的。重考率很高
: 我on campus interview 80%的题书里都有
: 除了上面的两道，还被问了OOD的扑克牌设计
| b**********5
发帖数: 7881 | 5 你会把你的总结， 写到你的blog上么？
【在 p*****2 的大作中提到】
:
: 我现在重点是system design了。CC150上的题目我总结过，而且很多题leetcode上也有
: 。CC150上的考到的概率确实很高。
| p*****2
发帖数: 21240 | 6
那个总结的比较简单。只发到了这个板上。
【在 b**********5 的大作中提到】
: 你会把你的总结， 写到你的blog上么？
| l*n
发帖数: 529 | 7 你说的system design是指的交互设计还是scalability设计？
【在 p*****2 的大作中提到】
:
: 那个总结的比较简单。只发到了这个板上。
| p*****2
发帖数: 21240 | 8
主要是distributed吧。scalability相关的。面试经常考的。
【在 l*n 的大作中提到】
: 你说的system design是指的交互设计还是scalability设计？
| l*n
发帖数: 529 | 9 能给几个例子吗？
【在 p*****2 的大作中提到】
:
: 主要是distributed吧。scalability相关的。面试经常考的。
| h**o
发帖数: 548 | 10 if (root == p || root == q) return root;
书上好像不是这样认为。see line 30-35.
我当时还比较了半天那。要这么简单就好了。不过这些题真是耗我的青春。
L&
【在 g****o 的大作中提到】
: 我是第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&
| h**o
发帖数: 548 | 11 请问二爷，你说这题重要。要面你，你用leetcode上的方法吗？ leetcode上的方法比
较好理解。但和cc150结果有出入。
【在 h**o 的大作中提到】
: if (root == p || root == q) return root;
: 书上好像不是这样认为。see line 30-35.
: 我当时还比较了半天那。要这么简单就好了。不过这些题真是耗我的青春。
:
: L&
| p****o
发帖数: 46 | 12 关于排列的问题，
你的方法相当于是 process-then-recur. 而CC150的方法是recur-then-process. 相比
之下,CC150写的是有点复杂.复杂度应该也是O(n!)吧,(不是很确定).
不过除了算法之外，很多代码写出来难易，也跟选择的语言，可供调用库接口，具体的
输入输出要求有很大关系.
顺便搭车问一句，谁有CC150第５版电子版? 能否发一个.
L&
【在 g****o 的大作中提到】
: 我是第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&
| f****8
发帖数: 72 | 13 请问二爷能给一总结的链接么？
刚才考古没有找到~~~
多谢了！
【在 p*****2 的大作中提到】
:
: 主要是distributed吧。scalability相关的。面试经常考的。
|
|
