请教个面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教个面试题

请教个面试题# JobHunting - 待字闺中

c*p2013-08-18 07:08

1 楼

given a binary tree, output it max sum of nodes. But the nodes should be
not adjacent to each other. In other word, if you use the root, you cannot
use its children because children and root are adjacent.
哪位大侠上段代码？

a*92013-08-18 07:08

2 楼

左右孩子算adj么？

c*p2013-08-18 07:08

3 楼

左右不是adj。只有parent和它的left, right是 adj

【在 a********9 的大作中提到】

: 左右孩子算adj么？

p*22013-08-18 07:08

4 楼

有没有例子？

c*p2013-08-18 07:08

5 楼

没啊，朋友的面试题，
我一看，好难啊。。。

【在 p*****2 的大作中提到】

: 有没有例子？

a*m2013-08-18 07:08

6 楼

dp
hashmap, int> mem;
int CalcMax(Node *node, bool flag) {
if (!node) return 0;
if (!mem.exist(node, flag)) {
if (flag) {
mem[node, flag] = CalcMax(node->left, false) + CalcMax(node->left,
false);
} else {
mem[node, flag] = max(CalcMax(node->left, false) + CalcMax(node->left,
false),
CalcMax(node->left, true) + CalcMax(node->left, true) +
node->value);
}
}
return mem[node, flag];
}

e*82013-08-18 07:08

7 楼

这个就和那个maximum independent set on a tree的问题差不多吧。
dp

c*p2013-08-18 07:08

8 楼

啊？请问那个是哪道题啊？
我也没看过你说的那个题。。。
能给个link么？

【在 e*******8 的大作中提到】

: 这个就和那个maximum independent set on a tree的问题差不多吧。
: dp

e*82013-08-18 07:08

9 楼

vazirani的算法书 chapter 6
Section 6.7
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

【在 c********p 的大作中提到】

: 啊？请问那个是哪道题啊？
: 我也没看过你说的那个题。。。
: 能给个link么？

c*p2013-08-18 07:08

10 楼

挖，这个好高级，没读过哦，谢谢了，我好好读读。。

【在 e*******8 的大作中提到】

: vazirani的算法书 chapter 6
: Section 6.7
: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

c*p2013-08-18 07:08

11 楼

虫子，我觉得这段代码写的好像不对呀。。。

left,

【在 a********m 的大作中提到】

: dp
: hashmap, int> mem;
: int CalcMax(Node *node, bool flag) {
: if (!node) return 0;
: if (!mem.exist(node, flag)) {
: if (flag) {
: mem[node, flag] = CalcMax(node->left, false) + CalcMax(node->left,
: false);
: } else {
: mem[node, flag] = max(CalcMax(node->left, false) + CalcMax(node->left,

c*p2013-08-18 07:08

12 楼

书写错了吧，那个例子，应该是2,4,6, 不是2, 3, 6吧？

【在 e*******8 的大作中提到】

: vazirani的算法书 chapter 6
: Section 6.7
: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

e*82013-08-18 07:08

13 楼

没有吧。书上只是要求size最大的（例子里那个tree，最大的independent set最多只
能有３个结点），不是结点的value之和最大的。每个结点的数字只是个id而已。
不过原理是一样的。

【在 c********p 的大作中提到】

: 书写错了吧，那个例子，应该是2,4,6, 不是2, 3, 6吧？

c*p2013-08-18 07:08

14 楼

Size指的是什么

【在 e*******8 的大作中提到】

: 没有吧。书上只是要求size最大的（例子里那个tree，最大的independent set最多只
: 能有３个结点），不是结点的value之和最大的。每个结点的数字只是个id而已。
: 不过原理是一样的。

e*82013-08-18 07:08

15 楼

size就是结点集合的大小。书里的那个例子有好几个最优解（因为最优解不一定是唯一
的，比如｛１，４，６｝，｛２，３，６｝，｛２，４，６｝的大小都是３，所以都是
最优解）。不过如果用dp的话，自然只会找出一个，具体找出哪一个，看你怎么写第归
公式了。这题只是要找出集合的大小，所以只会返回３；但是如果是要找出最优解里具
体的每个结点，按书里的那个第归公式，就会返回｛６，２，４｝。