路在何方 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

路在何方

路在何方# Biology - 生物学

x*i2015-09-01 07:09

1 楼

不知道以前有人贴过不？我是第一次见
把BT sibling 连起来，constant 内存.
1 -->null
2 --> 3 -->null
7 --> 8 -->null

s*r2015-09-01 07:09

2 楼

不光没收到确认信，一个多星期了什么消息也没有
正常吗？

c*u2015-09-01 07:09

3 楼

A*72015-09-01 07:09

4 楼

35岁生物医学女，学的是干细胞和癌症这两个方向，俩娃，老公目前在申请生物
faculty，自己就很弱-----Ph.D仅一篇10分左右文章，另有个不成功的postdoc （无
一作文章，只有两三片二作小文章），之后生了二宝后在家待了1年半无工作，前段时
间好不容易找到份公司的工作，由于自己的技术失误又被裁员（原因可能在于家里待的
时间长了，无法适应高效的科研节奏了），现在该走哪条路呢，除了在家带孩子外？

g*i2015-09-01 07:09

5 楼

老题了.

T*m2015-09-01 07:09

6 楼

正常的。

【在 s*****r 的大作中提到】

: 不光没收到确认信，一个多星期了什么消息也没有
: 正常吗？

O*n2015-09-01 07:09

7 楼

传统路线是夫妻老婆店

【在 A****7 的大作中提到】

: 35岁生物医学女，学的是干细胞和癌症这两个方向，俩娃，老公目前在申请生物
: faculty，自己就很弱-----Ph.D仅一篇10分左右文章，另有个不成功的postdoc （无
: 一作文章，只有两三片二作小文章），之后生了二宝后在家待了1年半无工作，前段时
: 间好不容易找到份公司的工作，由于自己的技术失误又被裁员（原因可能在于家里待的
: 时间长了，无法适应高效的科研节奏了），现在该走哪条路呢，除了在家带孩子外？

e*s2015-09-01 07:09

8 楼

没看懂

s*r2015-09-01 07:09

9 楼

多谢区长，那我就再耐心等等吧

t*a2015-09-01 07:09

10 楼

蹲家大妈-->database developer/Data analyst (usalaotu)

f*e2015-09-01 07:09

11 楼

BST?

s*y2015-09-01 07:09

12 楼

哈哈哈，老土又来了，看来今年大妈特别多，收成不错，好久没来拉客了

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

: 蹲家大妈-->database developer/Data analyst (usalaotu)

l*a2015-09-01 07:09

13 楼

const memory,
how to resolve it?

【在 g*****i 的大作中提到】

: 老题了.

A*72015-09-01 07:09

14 楼

这算是转行吗？应该自学些什么呢？多谢了！

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

: 蹲家大妈-->database developer/Data analyst (usalaotu)

g*i2015-09-01 07:09

15 楼

在链接第n层的时候,利用已经连接的n-1层,所以维系两个pointer就可以了.

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

: const memory,
: how to resolve it?

e*o2015-09-01 07:09

16 楼

他给你开玩笑的。

【在 A****7 的大作中提到】

: 这算是转行吗？应该自学些什么呢？多谢了！

l*a2015-09-01 07:09

17 楼

please share your code.thank
or explain how to use the n-1 layer

【在 g*****i 的大作中提到】

: 在链接第n层的时候,利用已经连接的n-1层,所以维系两个pointer就可以了.

t*a2015-09-01 07:09

18 楼

到版上考考古，留意一下echowuhao的帖子。听说女码工在IT界很紧缺。

【在 A****7 的大作中提到】

: 这算是转行吗？应该自学些什么呢？多谢了！

x*i2015-09-01 07:09

19 楼

我刚写了一遍，没有test
class node {
node *l;
node *r;
node *s;
};
void linksibling(node *root)
{
if (!root) return;
root->s = NULL;
node *c = root, *n, *h;
while (c)
{
// 找下一层的头
while (c && !c->l && !c->r)
c = c->s;
if (!c)
break;
if (c->l)
{
n = c->l;
h = n;
}
if (c->r)
{
if (n)
{
n->s = c->r;
n = c->r;
}
else {
n = c->r;
h = n;
}
}
// 链接下一层
while (c->s)
{
c = c->s;
if (c->l)
{
n->s = c->l;
n = n->s;
}
if (c->r)
{
n->s = c->r;
n = n->s;
}
}
n->s = NULL;
//
c = h;
}
}

K*g2015-09-01 07:09

20 楼

跟你的思路一样，不过找第一个结点可以优化以下
struct Node{
int value;
Node *left;
Node *right;
Node *sibling;
};
void connect_sibling(Node *root){
root->sibling = 0;
Node *cur, *dummy;
dummy = new Node;
while(root){
cur = dummy;
while(root){
if(root->left){
cur->sibling = root->left;
cur = root->left;
}
if(root->right){
cur->sibling = root->right;
cur = root->right;
}
root = root->sibling;
}
cur->sibling = 0;
root = dummy->sibling;
}
delete dummy;
}

【在 x***i 的大作中提到】

: 我刚写了一遍，没有test
: class node {
: node *l;
: node *r;
: node *s;
: };
: void linksibling(node *root)
: {
: if (!root) return;
: root->s = NULL;

x*i2015-09-01 07:09

21 楼

nice. simple is better, :-).

【在 K*******g 的大作中提到】

: 跟你的思路一样，不过找第一个结点可以优化以下
: struct Node{
: int value;
: Node *left;
: Node *right;
: Node *sibling;
: };
: void connect_sibling(Node *root){
: root->sibling = 0;
: Node *cur, *dummy;

d*l2015-09-01 07:09

22 楼

厉害！之前这个问题一直没想出特别简洁的办法，这个非常好

【在 K*******g 的大作中提到】

B*12015-09-01 07:09

23 楼

弱问，和1337大牛的这题有什么不同啊？
http://www.leetcode.com/2010/03/first-on-site-technical-intervi

v*n2015-09-01 07:09

24 楼

什么叫constant 内存

示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。

【在 x***i 的大作中提到】

: 不知道以前有人贴过不？我是第一次见
: 把BT sibling 连起来，constant 内存.
: 1 -->null
: 2 --> 3 -->null
: 7 --> 8 -->null

c*p2015-09-01 07:09

25 楼

O(1) space

【在 v***n 的大作中提到】

: 什么叫constant 内存
:
: 示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。

g*i2015-09-01 07:09

26 楼

1337的assume是full tree

【在 B*******1 的大作中提到】

: 弱问，和1337大牛的这题有什么不同啊？
: http://www.leetcode.com/2010/03/first-on-site-technical-intervi

i*e2015-09-01 07:09

27 楼

如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
上一层已经连接好的节点。

【在 g*****i 的大作中提到】

: 1337的assume是full tree

B*12015-09-01 07:09

28 楼

还以为大牛不来这里指点大家了。

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

: 如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
: 第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
: 上一层已经连接好的节点。

r*n2015-09-01 07:09

29 楼

太巧妙了
不过这种dummy node的trick，估计现场直接写出来，一看就是练过的

【在 K*******g 的大作中提到】

g*i2015-09-01 07:09

30 楼

又见大牛,恩你给的解法稍微改下就可以了

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

x*i2015-09-01 07:09

31 楼

如果用recursive for general case, space is O(n) in stack, the height of the
tree.

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

r*n2015-09-01 07:09

32 楼

假如不考虑recursive用的stack space,似乎还没想出来怎么稍微修改一下就能work?
大牛们，能详细解释下吗？

the

【在 x***i 的大作中提到】

: 如果用recursive for general case, space is O(n) in stack, the height of the
: tree.

g*x2015-09-01 07:09

33 楼

1337那第一个方法是tail recursive，很容易改成loop吧，
void connect_sibling( node * root)
{
if (!root) return;
root->sibling=0;
node * current_level_head=root;

while(current_level_head)
{
node *current_node=current_level_head;
node *next_level_head=0;
while (current_node)
{
if (current_node->left)
{
if (next_level_head==0)
next_level_head=current_node->left;

current_node->left->sibling=0;

if (current_node->right)
current_node->left->sibling=current_node_right;
else if (current_node->sibling)
{
if (current_node->sibling->left)
current_node->left->sibling=current_node->sibling->left;
else if (current_node->sibling->right)
current_node->left->sibling=current_node->sibling->right;
}
}
if (current_node->right)
{
if (next_level_head==0)
next_level_head=current_node->right;
current_node->right->sibling=0;
if (current_node->sibling)
{
if (current_node->sibling->left)
current_node->right->sibling=current_node->sibling->left;
else if (current_node->sibling->right)
current_node->right->sibling=current_node->sibling->
right;
}
}
current_node=current_node->sibling;
}//while (current_node)
current_level_head=next_level_head;
}//while(current_level_head)
}

a*m2015-09-01 07:09

34 楼

1337还是careerup有。

示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。

【在 x***i 的大作中提到】

: 不知道以前有人贴过不？我是第一次见
: 把BT sibling 连起来，constant 内存.
: 1 -->null
: 2 --> 3 -->null
: 7 --> 8 -->null

d*u2015-09-01 07:09

35 楼

这个算法太牛了，不知我的理解对不对？
void connect_sibling( Node *root ) {
root->sibling = null;
Node *cur, *dummy;
dummy = new Node;
while( root ) { //dummy->slibling是指向上次下一层的最左节点。
cur = dummy; //这样保证dummy->slibling总指向最左节点
while( root ) { // 找上一层的最右边节点，假设当前层sibling已连好。
if( root->left ) {
cur->sibling = root->left;
cur = root->left;
}
if(root->right){
cur->sibling = root->right;
cur = root->right;
}
root = root->sibling; //上一层的下一个姐妹，直到最右边。
} //end of while second loop
//此时，下一层已串好。
cur->sibling = null; //最右边下一层填空。
root = dummy->sibling; //上层的右一个节点。
}
delete dummy;
}

【在 K*******g 的大作中提到】

r*n2015-09-01 07:09

36 楼

大家在讨论不是去掉tail recursion，是怎么把1337的第一个方法改成支持not full
binary tree。
你这么写，意思跟KeithDeng的一样吧，代码上却没他的简洁。
在想怎么保留1337的recursion，还能支持所有的binary tree，觉得改动很大，不是大
牛们说的稍微改改

【在 g***x 的大作中提到】

: 1337那第一个方法是tail recursive，很容易改成loop吧，
: void connect_sibling( node * root)
: {
: if (!root) return;
: root->sibling=0;
: node * current_level_head=root;
:
: while(current_level_head)
: {
: node *current_node=current_level_head;