OD order 状态一问 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

OD order 状态一问

OD order 状态一问# PDA - 掌中宝

t*n2011-08-23 07:08

1 楼

Given a binary tree, how would you write program for getting mirror image of
tree in O(n) time? Is it possible ? Assume you have no constraints on space.
我只能想到递归:
Mirror(Node* p){
Mirror(p->left);
Mirror(p->right);
ExchangeLeftRight(p);
}
这个复杂度应该怎么算?

s*52011-08-23 07:08

2 楼

工作近两年，原本预计的升职一直迟迟未下来。一个月前老板口头说预计马上能升，现
在一个多月过去了，不知道什么情况。请问各个公司一般从老板行动提交升职到HR最终
批准下来是多久，好几个月？还是我目前的情况可能老板根本忘了，怎么去打听比较合
适？

s*n2011-08-23 07:08

3 楼

skydrive看不到skydrive synced storage. Goodreader也不支持skydrive。
skydrive synced storage->dropbox->goodreader这样会有问题么？

d*r2011-08-23 07:08

4 楼

在OD上抢了一个HP touchpad，现在状态是in the Warehouse。这状态有希望吗？
officemax的已经backorder了，希望OD这个不要再黄掉。

l*t2011-08-23 07:08

5 楼

Think how many times each node will be touched ...

a*a2011-08-23 07:08

6 楼

有戏
预计delivery什么时候到

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

: 在OD上抢了一个HP touchpad，现在状态是in the Warehouse。这状态有希望吗？
: officemax的已经backorder了，希望OD这个不要再黄掉。

b*v2011-08-23 07:08

7 楼

T(n)=2*T(n/2)+1
根据master theorem, 复杂度是O(n)

of
space.

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

: Given a binary tree, how would you write program for getting mirror image of
: tree in O(n) time? Is it possible ? Assume you have no constraints on space.
: 我只能想到递归:
: Mirror(Node* p){
: Mirror(p->left);
: Mirror(p->right);
: ExchangeLeftRight(p);
: }
: 这个复杂度应该怎么算?

d*r2011-08-23 07:08

8 楼

8月31号delivery
那天晚上本来先order了一个是8月26号delivery，后来发现SD上有人给code送15刀
subway giftcard，就把之前order取消了，重订了一个，变成31号delivery了。。。

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

: 有戏
: 预计delivery什么时候到

c*f2011-08-23 07:08

9 楼

mark

a*a2011-08-23 07:08

10 楼

office depot这次还算厚道，既然你的不是back order，应该没问题。
我没贪心这15块
一次下当
刚刚收到confirmation

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

: 8月31号delivery
: 那天晚上本来先order了一个是8月26号delivery，后来发现SD上有人给code送15刀
: subway giftcard，就把之前order取消了，重订了一个，变成31号delivery了。。。

c*f2011-08-23 07:08

11 楼

这个应该等价二叉树的遍历
那么T(n)=2T(n/2)+O(1)
适用master theory的其中一种情况
当有ε > 0，使得f(n)=O(n^(logb(a)-ε))则T(n)=Theta(n^logb(a))
这里a=2,b=2,logb(a)=1, f(n)=O(1), 所以存在epsilon=1
那么 T（n）=Theta(n)

z*y2011-08-23 07:08

12 楼

Check the code below:
void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

f*r2011-08-23 07:08

13 楼

That's an O(N) algorithm (each node is only touched once). Be careful about
the boundary conditions though (i.e. check for NULL for p->left & p->right).

of
space.

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