b*n
2 楼
想上的可以搞这个，authorized dealer，价格也还成
http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
t*h
3 楼
LCA？ 是二叉树吗？ 150上有原题吧，不过不是最优的，递归套递归，如果稍作改变，
可以只递归一次。不知道你给的哪种？
move on。。。更好的在后面
【在 p****2 的大作中提到】
: 自我感觉还好，lowest parent of two nodes in a tree，不知为何没成。有经验的说
: 说？
可以只递归一次。不知道你给的哪种？
move on。。。更好的在后面
【在 p****2 的大作中提到】
: 自我感觉还好，lowest parent of two nodes in a tree，不知为何没成。有经验的说
: 说？
r*5
4 楼
等崩到2k再说
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
y*u
5 楼
这题挺难的
标准做法是range minimum query
靠，现在的电面题都不会做了。。。
【在 p****2 的大作中提到】
: 自我感觉还好，lowest parent of two nodes in a tree，不知为何没成。有经验的说
: 说？
标准做法是range minimum query
靠，现在的电面题都不会做了。。。
【在 p****2 的大作中提到】
: 自我感觉还好，lowest parent of two nodes in a tree，不知为何没成。有经验的说
: 说？
d*l
6 楼
hotdigital 到底是和什么一家的
在canon list上面找不到他，但大家都说是authorized
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
在canon list上面找不到他，但大家都说是authorized
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
t*h
7 楼
完全不懂你在说什么啊
【在 y**********u 的大作中提到】
: 这题挺难的
: 标准做法是range minimum query
: 靠，现在的电面题都不会做了。。。
【在 y**********u 的大作中提到】
: 这题挺难的
: 标准做法是range minimum query
: 靠，现在的电面题都不会做了。。。
d*l
8 楼
re
同等
【在 r*********5 的大作中提到】
: 等崩到2k再说
同等
【在 r*********5 的大作中提到】
: 等崩到2k再说
f*t
9 楼
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 t**********h 的大作中提到】
: 完全不懂你在说什么啊
【在 t**********h 的大作中提到】
: 完全不懂你在说什么啊
t*e
10 楼
它家卖第一个就是 $2449.95，被俺拿下，后来它又涨到 $2499.95，再降回来。。。
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
【在 b******n 的大作中提到】
: 想上的可以搞这个，authorized dealer，价格也还成
: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=300420450172
t*h
11 楼
多谢。
我只会150上的版本，赶紧学学这个版本
【在 f*******t 的大作中提到】
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
我只会150上的版本，赶紧学学这个版本
【在 f*******t 的大作中提到】
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
A*h
12 楼
又降啦！？
我忍，到五月初在说。
我忍，到五月初在说。
i*e
13 楼
面试不会让你写那么复杂算法的。
递归程序就只用五行，O(N) 复杂度。
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
递归程序就只用五行，O(N) 复杂度。
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
p*y
14 楼
Re, same here! But I will (so should) wait even longer.
【在 A****h 的大作中提到】
: 又降啦！？
: 我忍，到五月初在说。
【在 A****h 的大作中提到】
: 又降啦！？
: 我忍，到五月初在说。
w*z
15 楼
这个好，看得懂，记得住。
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
A*h
16 楼
haha
【在 p*******y 的大作中提到】
: Re, same here! But I will (so should) wait even longer.
【在 p*******y 的大作中提到】
: Re, same here! But I will (so should) wait even longer.
H*r
17 楼
Very nice article!
那个5行的Bottom-up Approach (Worst case O(n) )
怎么感觉对degenerate tree仍然是O(N*N)?
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
那个5行的Bottom-up Approach (Worst case O(n) )
怎么感觉对degenerate tree仍然是O(N*N)?
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
p*y
18 楼
似乎确实是的，官方名字是“Focus Camera Inc.”，你看看这个帖子：http://m.slic
kdeals.net/forums/showthread.php?t=1945972
【在 d********l 的大作中提到】
: hotdigital 到底是和什么一家的
: 在canon list上面找不到他，但大家都说是authorized
kdeals.net/forums/showthread.php?t=1945972
【在 d********l 的大作中提到】
: hotdigital 到底是和什么一家的
: 在canon list上面找不到他，但大家都说是authorized
s*a
19 楼
no need for recursion. just trace back from each node to root, and print out
the first common ancester..(it should be log(N) for a binary tree ?)
the first common ancester..(it should be log(N) for a binary tree ?)
i*e
20 楼
每个 node 最多只遍历一次。
【在 H****r 的大作中提到】
: Very nice article!
: 那个5行的Bottom-up Approach (Worst case O(n) )
: 怎么感觉对degenerate tree仍然是O(N*N)?
【在 H****r 的大作中提到】
: Very nice article!
: 那个5行的Bottom-up Approach (Worst case O(n) )
: 怎么感觉对degenerate tree仍然是O(N*N)?
i*e
21 楼
You need to ask interviewer whether there's a parent node.
It makes a big difference in the algorithm.
If there's parent node, it can be improved to O(h) , h = height of tree.
out
【在 s*******a 的大作中提到】
: no need for recursion. just trace back from each node to root, and print out
: the first common ancester..(it should be log(N) for a binary tree ?)
It makes a big difference in the algorithm.
If there's parent node, it can be improved to O(h) , h = height of tree.
out
【在 s*******a 的大作中提到】
: no need for recursion. just trace back from each node to root, and print out
: the first common ancester..(it should be log(N) for a binary tree ?)
s*a
22 楼
but there is always parent node (except for the root) since it is a tree.
I guess you meant the implementation (e.g., array vs linked data structure
via pointers), but that should be irrelevant at the algorithmic level..
【在 i**********e 的大作中提到】
: You need to ask interviewer whether there's a parent node.
: It makes a big difference in the algorithm.
: If there's parent node, it can be improved to O(h) , h = height of tree.
:
: out
I guess you meant the implementation (e.g., array vs linked data structure
via pointers), but that should be irrelevant at the algorithmic level..
【在 i**********e 的大作中提到】
: You need to ask interviewer whether there's a parent node.
: It makes a big difference in the algorithm.
: If there's parent node, it can be improved to O(h) , h = height of tree.
:
: out
t*h
23 楼
我擦，这个好，帅
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
i*e
24 楼
for a REAL tree there's a root.
but in computer science, usually tree is defined as:
struct Node {
Node *left;
Node *right;
};
You cannot assume that each node has a parent node. Actually this is a great
question to ask your interviewer, because you're responsible for finding
out the requirements.
Trust me, besides your coding/algorithmic skills, you'll also be evaluated
on whether you ask questions to find out requirements for a vaguely defined
problem.
【在 s*******a 的大作中提到】
: but there is always parent node (except for the root) since it is a tree.
: I guess you meant the implementation (e.g., array vs linked data structure
: via pointers), but that should be irrelevant at the algorithmic level..
but in computer science, usually tree is defined as:
struct Node {
Node *left;
Node *right;
};
You cannot assume that each node has a parent node. Actually this is a great
question to ask your interviewer, because you're responsible for finding
out the requirements.
Trust me, besides your coding/algorithmic skills, you'll also be evaluated
on whether you ask questions to find out requirements for a vaguely defined
problem.
【在 s*******a 的大作中提到】
: but there is always parent node (except for the root) since it is a tree.
: I guess you meant the implementation (e.g., array vs linked data structure
: via pointers), but that should be irrelevant at the algorithmic level..
H*r
25 楼
root
/ \
L1 R1
\
R2
...
Rn
/ \
a b
LCA(root, a, b) 总计算量大概是：
n+(n-1)+... + 1 ~= n*(n-1)/2
which is O(N*N)?
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
/ \
L1 R1
\
R2
...
Rn
/ \
a b
LCA(root, a, b) 总计算量大概是：
n+(n-1)+... + 1 ~= n*(n-1)/2
which is O(N*N)?
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
s*a
26 楼
谢谢,明白了。我一般都是习惯从graph的角度想算法，很少从data structure的level
想问题。在我的头脑里algorithm和data structure/code是完全独立的两个东西。可能
是学生的通病吧 :p
这题要是考试的话我会写两个function：一是bottom-up trace-back来找lowest
common ancester, 二是给定一个Node，找他的直接的parent node :p
great
【在 i**********e 的大作中提到】
: for a REAL tree there's a root.
: but in computer science, usually tree is defined as:
: struct Node {
: Node *left;
: Node *right;
: };
: You cannot assume that each node has a parent node. Actually this is a great
: question to ask your interviewer, because you're responsible for finding
: out the requirements.
: Trust me, besides your coding/algorithmic skills, you'll also be evaluated
想问题。在我的头脑里algorithm和data structure/code是完全独立的两个东西。可能
是学生的通病吧 :p
这题要是考试的话我会写两个function：一是bottom-up trace-back来找lowest
common ancester, 二是给定一个Node，找他的直接的parent node :p
great
【在 i**********e 的大作中提到】
: for a REAL tree there's a root.
: but in computer science, usually tree is defined as:
: struct Node {
: Node *left;
: Node *right;
: };
: You cannot assume that each node has a parent node. Actually this is a great
: question to ask your interviewer, because you're responsible for finding
: out the requirements.
: Trust me, besides your coding/algorithmic skills, you'll also be evaluated
H*r
27 楼
Unless the LCA for nodes that's processed has memory otherwise it's still
gona be processed it seems...
// code from the article: ///
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
}
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
gona be processed it seems...
// code from the article: ///
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
}
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
v*c
28 楼
T(n) = T(m1) + T(m2) + O(1), where m1+m2+1=n
so T(n) = O(n)
L&
【在 H****r 的大作中提到】
: Unless the LCA for nodes that's processed has memory otherwise it's still
: gona be processed it seems...
: // code from the article: ///
: 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&
so T(n) = O(n)
L&
【在 H****r 的大作中提到】
: Unless the LCA for nodes that's processed has memory otherwise it's still
: gona be processed it seems...
: // code from the article: ///
: 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*r
29 楼
建议加到onlinejudge!
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
【在 i**********e 的大作中提到】
: 面试不会让你写那么复杂算法的。
: 递归程序就只用五行，O(N) 复杂度。
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
H*r
30 楼
这是在每个node都有记忆的情况下才成立的啊
L&
【在 v****c 的大作中提到】
: T(n) = T(m1) + T(m2) + O(1), where m1+m2+1=n
: so T(n) = O(n)
:
: L&
L&
【在 v****c 的大作中提到】
: T(n) = T(m1) + T(m2) + O(1), where m1+m2+1=n
: so T(n) = O(n)
:
: L&
a*o
31 楼
怎么找leetcode上面所有的文章啊？
great
【在 i**********e 的大作中提到】
: for a REAL tree there's a root.
: but in computer science, usually tree is defined as:
: struct Node {
: Node *left;
: Node *right;
: };
: You cannot assume that each node has a parent node. Actually this is a great
: question to ask your interviewer, because you're responsible for finding
: out the requirements.
: Trust me, besides your coding/algorithmic skills, you'll also be evaluated
great
【在 i**********e 的大作中提到】
: for a REAL tree there's a root.
: but in computer science, usually tree is defined as:
: struct Node {
: Node *left;
: Node *right;
: };
: You cannot assume that each node has a parent node. Actually this is a great
: question to ask your interviewer, because you're responsible for finding
: out the requirements.
: Trust me, besides your coding/algorithmic skills, you'll also be evaluated
H*r
32 楼
Got it now.
What if the root is not guaranteed to be the common ancestor?
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
What if the root is not guaranteed to be the common ancestor?
【在 i**********e 的大作中提到】
: 每个 node 最多只遍历一次。
r*e
33 楼
the code will return NULL which means no LCA in the tree for
the two given nodes.
【在 H****r 的大作中提到】
: Got it now.
: What if the root is not guaranteed to be the common ancestor?
the two given nodes.
【在 H****r 的大作中提到】
: Got it now.
: What if the root is not guaranteed to be the common ancestor?
f*0
34 楼
只有两个node都不在tree里面的时候才会返回NULL吧。如果一个node在，另外一个node
不在，貌似返回的不是NULL。。而是指向存在的那个node的指针。。
另外top-down的方法改进一下可以解决求N个nodes的LCA，而down-top的看起来不可以
。。
【在 r*****e 的大作中提到】
: the code will return NULL which means no LCA in the tree for
: the two given nodes.
相关阅读