android自由过度了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

android自由过度了

android自由过度了# PDA - 掌中宝

h*e2014-11-26 08:11

1 楼

【以下文字转载自 board 讨论区】
发信人: Ameili (（天使爱美丽）), 信区: board
标题: [FW TEXAS] 本人继续爆 (转载)
发信站: BBS 未名空间站 (Wed Apr 27 17:17:53 2011, 美东)
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标题: [FW TEXAS] 本人继续爆
发信站: BBS 未名空间站 (Wed Apr 27 12:08:18 2011, 美东)
Fly哥的料爆了，很多人也不会相信，
为什么呢？他太精明。
一般初次或者数次跟他有过接触
的人都会对他热心助人的形象留下
深刻印象。他也确实会帮新人一些
小忙，给一些小恩惠。
如果你想被他骚扰，你必须满足以下条件。
必须年轻漂亮，至少Fly哥觉得你
没有损伤到他的视觉神经。
必须喜欢出来玩。
尤其是唱歌，喜欢喝酒更好。
最好每周末都这么度过。
对现任伴侣有怨言不满。
满足以上条件，恭喜你。
你就是Fly哥首选骚扰对象。
他的聚会总是能有年轻漂亮
刚来Houston没多久的美眉，去过
的人应该知道。
这是Fly哥组织聚会的一大卖点。
资深的，在Houston时间长了美女，
谁还出来跟他玩啊？
另外骚扰你之前，Fly哥会做各种各样
小心翼翼的试探，
毕竟他这么有名的人，要是对方一怒
之下出来爆他还是很麻烦。
如果你反应不如他预期，马上就龟缩，换另外一个态度。
你没有被骚扰过？很明显，你不符合以上条件。
Fly哥硕士没念完，拿了绿卡，并且上了移
民局的黑名单，有10年没回国了。
所以他的自以为是，一厢情愿，完全和当今
社会脱轨的想法真令人哭笑不得。
在这里我深表遗憾同情，多久没见父母了？
他从不隐瞒他已婚，这是他精明的地方。
请问他是否在聚会中主动提及他老婆？
是否在聚会中主动携伴出席过？
有的，可是对方不是他老婆。
不隐瞒，不主动，除非你去问他
这厮不仅是一个伪君子，披着羊皮的狼，
更是不知道天高地厚的人。
35+了，混成这样，LOL
Fly哥哥很蛋定，在华人的高楼和TX版面
回文都保持了受过高等教育的本色。不停致谢。
一边在MSN上到处拉人去support他。
该说的本人都说了，Fly哥有没有骚扰过别人，
他自己心里最清楚。
只要是发生过的，女孩子圈里会慢慢传开，
人在做，天在看。

w*g2014-11-26 08:11

2 楼

就一道题目没见过，就不说具体是三家中的哪家了。
要求先根遍历一棵树。
不是binary tree。
每个parent都可以有很多children。各个parent的children数目可以不同。
node不知道自己的sibling。没有指向sibling的指针。
parent自己存了一个链表，里面是指向所有children的指针。
这棵树有几百万个node，所以不能一次pre-order travel完，因为内存不够大。
所以需要分多次遍历。
第一次从root开始pre-order遍历100个node，然后记住这第100个node的位置。
第二次就直接从第100个node开始先根遍历。
第三次就直接从第200个node开始先根遍历。。。
知道所有node都遍历完。
这里的第100、200个node是指：如果一次性把所有的几百万个node都先根走完的话所碰
到的第100、200个node。
所以题目就是问如何多次分块遍历一棵树。
要求用递归写，但是可以使用stack。
我想了想觉得很复杂，然后就跪了。

g*c2014-11-26 08:11

3 楼

以至于每个app的setting都藏在不同的地方。

l*a2014-11-26 08:11

4 楼

用stack 存储root ==> current node的path是不是就可以了
如果当前有left child,下一个就是left child
否则如果当前有right child,下一个就是right child
否则如果是parent的left child,parent 有right child就去right child
否则再往上找。。。

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

: 就一道题目没见过，就不说具体是三家中的哪家了。
: 要求先根遍历一棵树。
: 不是binary tree。
: 每个parent都可以有很多children。各个parent的children数目可以不同。
: node不知道自己的sibling。没有指向sibling的指针。
: parent自己存了一个链表，里面是指向所有children的指针。
: 这棵树有几百万个node，所以不能一次pre-order travel完，因为内存不够大。
: 所以需要分多次遍历。
: 第一次从root开始pre-order遍历100个node，然后记住这第100个node的位置。
: 第二次就直接从第100个node开始先根遍历。

s*32014-11-26 08:11

5 楼

1. 用stack记录路径中的node.
2. 一个pointer记录停下来之后的那个点的node. 比如在100停下来，那么就记录第101
个node.
3. 接着从pointer开始递归.直到stack is Empty.

h*62014-11-26 08:11

6 楼

我不太明白的一点是图太大节点太多内存储存不下来那么是说DFS的时候深度太深所
以堆栈会溢出？那么为什么把每一层分块就能避免这个问题？因为虽然横向分块了但是
纵向深度还是不变的吧？

s*32014-11-26 08:11

7 楼

面试官的意思大致应该是call stack有限，但heap内存有很多。
比如你去JVM里写个递归算加法调用几千次，应该会抛stack overflow，但用循环肯定
没事。
题目里说可以用stack, 其实就是把call stack中的东西放到heap中去。

【在 h******6 的大作中提到】

: 我不太明白的一点是图太大节点太多内存储存不下来那么是说DFS的时候深度太深所
: 以堆栈会溢出？那么为什么把每一层分块就能避免这个问题？因为虽然横向分块了但是
: 纵向深度还是不变的吧？

q*m2014-11-26 08:11

8 楼

也就是说用 stack 的iterative的方法就可以了吗，看来也是leetcodee的题目？

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

: 面试官的意思大致应该是call stack有限，但heap内存有很多。
: 比如你去JVM里写个递归算加法调用几千次，应该会抛stack overflow，但用循环肯定
: 没事。
: 题目里说可以用stack, 其实就是把call stack中的东西放到heap中去。

h*62014-11-26 08:11

9 楼

那就是用stack写个iterative的dfs就行了？

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

s*32014-11-26 08:11

10 楼

题目要求用递归。直接iterative的话就不需要考虑call stack了不是吗？
也就是说，递归遍历前100个，遍历的同时要把上层的点(也就是你的call stack) 储存
到stack里。
结束第一次递归后释放了call stack内存，然后接着递归第101~200。
这时候就需要用到stack，不然你现在的call stack是空的，你不知道你上次递归调完
后call stack里有什么。

【在 h******6 的大作中提到】

:
: 那就是用stack写个iterative的dfs就行了？

s*x2014-11-26 08:11

11 楼

几百万个 nodes, 2^20 = 1M, 2^30=1B.
30 个 level 的 stack 还能不 work?
something is not alright.
前一阵有个题是让你做 BFS, 然后问你内存不够大时怎么做 BFS, 答案 leetcode 上
有个 solution, 就是用 DFS 的办法做 BFS.
这样更 make sense.

s*32014-11-26 08:11

12 楼

如果call stack内存够的话直接pre-order一遍不是完了么？

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

: 几百万个 nodes, 2^20 = 1M, 2^30=1B.
: 30 个 level 的 stack 还能不 work?
: something is not alright.
: 前一阵有个题是让你做 BFS, 然后问你内存不够大时怎么做 BFS, 答案 leetcode 上
: 有个 solution, 就是用 DFS 的办法做 BFS.
: 这样更 make sense.

m*k2014-11-26 08:11

13 楼

与100, 200有关系么？
1. set lastPoped = null,
2. print root,
3. push root into a stack S,
3. while (s.size()>0):
if not s.peek().hasChildren():
lastPoped = s.pop()
else:
s.push(s.peek().getSibling(lastPoped) )

Node.getSibling(Node childX) will return first Child if childX is null,
otherwise return x's next sibling.
看来来出题人默认stack不会out of mem，否者来个极端的例子，内存只允许stack存2
个Node，没法玩了。
或者也许我理解错了题意？

w*g2014-11-26 08:11

14 楼

你说得对，面试官当时对我说问题的关键就是你所说的“然后接着递归第101~200”。
就这一步怎么做？
我已经用stack把从根到第101个节点的path记录下来了。
（只记录了类似root - child - grand child - ...... - 101节点，这样的路径）

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

: 题目要求用递归。直接iterative的话就不需要考虑call stack了不是吗？
: 也就是说，递归遍历前100个，遍历的同时要把上层的点(也就是你的call stack) 储存
: 到stack里。
: 结束第一次递归后释放了call stack内存，然后接着递归第101~200。
: 这时候就需要用到stack，不然你现在的call stack是空的，你不知道你上次递归调完
: 后call stack里有什么。

l*62014-11-26 08:11

15 楼

struct node;
void print100(stack& waitStack);
struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
void print(node* root)
{
if(!root)
return;
childList* dummy = new childList();
dummy -> curNode = root;
dummy -> next = NULL;
stack waitStack;
waitStack.push(dummy);
while(!waitStack.empty())
{
print100(waitStack);
}
delete dummy;
}
void print100(stack& waitStack)
{
for(int i = 0 ; i < 100 ; i++)
{
if(waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
}
}

w*g2014-11-26 08:11

16 楼

这个方法没有用递归。题目要求必须用递归才行。我觉得这才是最难的地方。如果用
iteration，一个for循环就能实现向右的移动。可是如果必须用递归，怎么解决递归向
右和依靠push右侧兄弟导致的重复呢？
我的解决办法是：
任何一个node都只向下递归打印第一个child；
除了叶子以外，任何node都不向右递归自己的sibling；
只有叶子才向右侧递归打印；
只有当前node没有右侧的sibling时才递归打印栈顶的node，
这个栈顶的node其实就是当前node的先根遍历时的next node。
很多特殊情况还没考虑，但是大意就是这样。明天写一下code。

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

: struct node;
: void print100(stack& waitStack);
: struct childList{
: node* curNode;
: childList* next;
: };
: struct node{
: void* data;
: childList* children;
: };

l*62014-11-26 08:11

17 楼

void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
}

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

: 这个方法没有用递归。题目要求必须用递归才行。我觉得这才是最难的地方。如果用
: iteration，一个for循环就能实现向右的移动。可是如果必须用递归，怎么解决递归向
: 右和依靠push右侧兄弟导致的重复呢？
: 我的解决办法是：
: 任何一个node都只向下递归打印第一个child；
: 除了叶子以外，任何node都不向右递归自己的sibling；
: 只有叶子才向右侧递归打印；
: 只有当前node没有右侧的sibling时才递归打印栈顶的node，
: 这个栈顶的node其实就是当前node的先根遍历时的next node。
: 很多特殊情况还没考虑，但是大意就是这样。明天写一下code。

s*x2014-11-26 08:11

18 楼

这个就是变相的问你iterative preorder scan 怎么整？

w*g2014-11-26 08:11

19 楼

太强了！！！你的最后一行code我写了很多行实现，分了各种情况。看了你的code，才
发现其实那么多种情况本质上就是递归调用到栈顶，顿时佩服得五体投地。万分感谢赐
教！

void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
}

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

:
: void printn(stack& waitStack , int n)
: {
: if(n == 0 || waitStack.empty())
: return;
: childList* curHead = waitStack.top();
: waitStack.pop();
: dealWith(curHead -> curNode -> data);
: if(curHead -> next)
: waitStack.push(curHead -> next);

f*n2014-11-26 08:11

20 楼

mark

z*u2014-11-26 08:11

21 楼

不清楚这里的 "curHead -> next" 是不是在使用指向sibling的指针？题目中不是说没
有指向sibling的指针么？还是我理解错了？

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

z*u2014-11-26 08:11

22 楼

楼主啊，他的代码这里的 "curHead -> next" 貌似使用了指向sibling的指针，不是没
有指向sibling的指针么？
我怎么觉得这一题就是iterative inorder 的题目呢，只是不是binary tree而已。pop
一次，n++,till n==100或者stack.empty(). chenglg的代码本质就是用了吧while(n++
<100) 改成了 f(n) = sth + f(--n)而已。

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

: 太强了！！！你的最后一行code我写了很多行实现，分了各种情况。看了你的code，才
: 发现其实那么多种情况本质上就是递归调用到栈顶，顿时佩服得五体投地。万分感谢赐
: 教！
:
: void printn(stack& waitStack , int n)
: {
: if(n == 0 || waitStack.empty())
: return;
: childList* curHead = waitStack.top();
: waitStack.pop();

c*p2014-11-26 08:11

23 楼

mark

p*o2014-11-26 08:11

24 楼

“内存都够大。只是打印机的内存不够大，不能一次把所
有的node都存在打印机内存里，所以需要分批次打印。” 是什么意思？
整棵树在不在内存里？
如果在内存里，那么把遍历过程简单地写成迭代器，
每次不就可以从上次暂停的地方继续遍历和打印了？
是不是树太大要放磁盘上，每次只能载一部分到内存里，而你没有理解题意？

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

y*t2014-11-26 08:11

25 楼

mark

l*62014-11-26 08:11

26 楼

struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
curHead is a pointer of childList type , not a node type. childlist have
sibling pointer while node doesn't have.
It is true it is only a preorder iterative traverse, the point is to modify
the code so that parameter can be passed to the printn() function nicely.

【在 z****u 的大作中提到】

: 不清楚这里的 "curHead -> next" 是不是在使用指向sibling的指针？题目中不是说没
: 有指向sibling的指针么？还是我理解错了？

w*k2014-11-26 08:11

27 楼

mark

w*l2014-11-26 08:11

28 楼

请问 CHILDLIST* next 什么时候会被赋值（不为null）？
在dealwith（）funct 里面吗？

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

: struct node;
: void print100(stack& waitStack);
: struct childList{
: node* curNode;
: childList* next;
: };
: struct node{
: void* data;
: childList* children;
: };

r*h2014-11-26 08:11

29 楼

感觉树像文件系统的目录结构，企业环境中数百万个文件和目录的文件系统太常见了，
要求的前序遍历像unix命令tree。关键是如果栈溢出时，就得把栈的内容写入磁盘，比
如一次写一个文件，栈空的时候再按后写先读的顺序把文件一个个读入栈进行处理，其
余就是典型的前序遍历的算法。还可以考虑多线程双缓冲，这样遍历和栈的磁盘读写都
可以同时进行了。

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

f*n2014-11-26 08:11

30 楼

mark

l*12014-11-26 08:11

31 楼

试着写了一个，求指导。
print100(Stack stack, TreeNode root, int index){
if(stack.isEmpty()) return;
if(index==101) return;
System.out.println(root.val);
stack.push(root);
if(root.left!=null)
print100(stack, root.left, index+1);
else if(root.right!=null)
print100(stack, root.right, index+1);
else{
while(!stack.isEmpty() && root.right==null){
root=stack.pop();
}
print100(stack, root.right, index+1);
}
}
initialize
Stack stack = new Stack();
stack.add(root);
every time when call method:
if(!stack.isEmpty){
TreeNode root=stack.pop();
print100(stack, root, 0);
}