奔我小侄写的诗 -- New York City (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Parenting - 为人父母

奔我小侄写的诗 -- New York City (转载)

奔我小侄写的诗 -- New York City (转载)# Parenting - 为人父母

r*n2011-12-16 08:12

1 楼

材料：排骨1磅，土豆一个，香菜，老抽，郫县豆瓣2勺，大蒜2瓣，老姜适量，八角四
个，花椒，红糖
1.排骨过水打掉泡沫，洗净
2.土豆去皮切成块
3.大蒜老姜切成块
4.油烧八分热，放入花椒大蒜老姜，郫县豆瓣炒香
5.放入排骨和土豆翻炒1分钟，加入水刚好没过排骨和土豆，加入一点老抽（先尝一下
汤汁咸淡），一勺红糖调色
6.大火烧到汁水差不多干了就好了。最后加香菜
http://blog.sina.com.cn/s/blog_672e102801011cfv.html
顺便问下怎么砍排骨？我这里只有一家中国店，没有排骨卖。我用砍刀是怎么也看不断
，倒砍出一堆骨头渣

f*z2011-12-16 08:12

2 楼

careercup上看到的，没有想到好的办法。
题目：
Convert a min heap to BST without changing its structure and
of course no extra space

k*n2011-12-16 08:12

3 楼

【以下文字转载自 Piebridge 讨论区】
发信人: hasqure (晚上10点之后上网, 多谢谅解), 信区: Piebridge
标题: 奔我小侄写的诗 -- New York City
发信站: BBS 未名空间站 (Thu Dec 15 19:13:11 2011, 美东)
10岁的小侄，夏天和我去纽约度假
New York City
New York City, oh what a wonderful place,
But for 22.2 million people, there's not much space.
I wish I could be there, anytime at all,
To go to Times Square, and Carnegie Hall.
I would shop on Fifth Avenue, and watch a Broadway show,
Eat lunch by the Hudson River, and watch that water flow.
I would go to Lady Liberty, a man-made landmark,
Rockefeller Center, and also Central Park.
I would take a visit to Madison Square Garden, and the Brooklyn Bridge too,
The Empire State Building, and the Central Park zoo.
It's always worth the trip to go to the United Nations,
And the Metropolitan Museum to see master's creations.
But never forget Grand Central Station,
For it's the place you'll go, if you want a subway vacation.
But what really that sets New York apart,
Is the kindness in everybody's heart.

S*s2011-12-16 08:12

4 楼

很赞呀！

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

: 材料：排骨1磅，土豆一个，香菜，老抽，郫县豆瓣2勺，大蒜2瓣，老姜适量，八角四
: 个，花椒，红糖
: 1.排骨过水打掉泡沫，洗净
: 2.土豆去皮切成块
: 3.大蒜老姜切成块
: 4.油烧八分热，放入花椒大蒜老姜，郫县豆瓣炒香
: 5.放入排骨和土豆翻炒1分钟，加入水刚好没过排骨和土豆，加入一点老抽（先尝一下
: 汤汁咸淡），一勺红糖调色
: 6.大火烧到汁水差不多干了就好了。最后加香菜
: http://blog.sina.com.cn/s/blog_672e102801011cfv.html

S*n2011-12-16 08:12

5 楼

min heap->linkedlist->BST

structure and

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

: careercup上看到的，没有想到好的办法。
: 题目：
: Convert a min heap to BST without changing its structure and
: of course no extra space

y*u2011-12-16 08:12

6 楼

nice
有才

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

: 【以下文字转载自 Piebridge 讨论区】
: 发信人: hasqure (晚上10点之后上网, 多谢谅解), 信区: Piebridge
: 标题: 奔我小侄写的诗 -- New York City
: 发信站: BBS 未名空间站 (Thu Dec 15 19:13:11 2011, 美东)
: 10岁的小侄，夏天和我去纽约度假
: New York City
: New York City, oh what a wonderful place,
: But for 22.2 million people, there's not much space.
: I wish I could be there, anytime at all,
: To go to Times Square, and Carnegie Hall.

F*t2011-12-16 08:12

7 楼

看上去, 你这个是baby backrib吧?
这个一般还很难砍动的, 很硬
如果是sparerib的话比较好砍

h*i2011-12-16 08:12

8 楼

如果不破坏,我觉得没有额外空间不行吧.

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

: careercup上看到的，没有想到好的办法。
: 题目：
: Convert a min heap to BST without changing its structure and
: of course no extra space

k*b2011-12-16 08:12

9 楼

写得好。读起来朗朗上口，有点 Robert Frost 的Stopping By Woods on a Snowy
Evening的味道。
才十岁大的孩子。

c*n2011-12-16 08:12

10 楼

很辣吗？

f*z2011-12-16 08:12

11 楼

你的意思是这个heap是链接起来的，而不是通常的用一个array表示的？

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

: min heap->linkedlist->BST
:
: structure and

r*n2011-12-16 08:12

12 楼

是的，原来还有这个区别阿，下次去买sparerib。谢谢啦

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

: 看上去, 你这个是baby backrib吧?
: 这个一般还很难砍动的, 很硬
: 如果是sparerib的话比较好砍

f*z2011-12-16 08:12

13 楼

我觉得意思是heap跟BST都是binary tree, 保持structure只是保持树形，里面的内容
当然移动了。

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

: 如果不破坏,我觉得没有额外空间不行吧.

r*n2011-12-16 08:12

14 楼

我觉得一点都不辣。。。但是我两岁就开始吃辣椒，所以要看你吃不吃辣了：P

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

: 很辣吗？

S*n2011-12-16 08:12

15 楼

yes

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

: 你的意思是这个heap是链接起来的，而不是通常的用一个array表示的？

t*02011-12-16 08:12

16 楼

看着就好吃，尤其喜欢这里面的土豆，入口即化吧？

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

g*s2011-12-16 08:12

17 楼

then how to ensure the heap operations' complexity is still O(logN)? for
linked list you can't randomly access the element.
why not assuming the heap is also a binary tree? the array format of heap
is just a compact representation of heap.
even if the input heap is represented as an array, we can still store the
newly bst to the array. but it would need O(1) space for array element
swap. i think this is OK.

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

: yes

c*n2011-12-16 08:12

18 楼

呵呵，看着红红的图片和郫县豆瓣2勺的字样，已经开始觉得辣了

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

: 我觉得一点都不辣。。。但是我两岁就开始吃辣椒，所以要看你吃不吃辣了：P

f*z2011-12-16 08:12

19 楼

这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
所以operation仍然是O(logN).
对于用array表示的heap和BST, 怎么样来转换呢？

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

: then how to ensure the heap operations' complexity is still O(logN)? for
: linked list you can't randomly access the element.
: why not assuming the heap is also a binary tree? the array format of heap
: is just a compact representation of heap.
: even if the input heap is represented as an array, we can still store the
: newly bst to the array. but it would need O(1) space for array element
: swap. i think this is OK.

r*n2011-12-16 08:12

20 楼

不过我是觉得稍微有点过头了，我喜欢吃稍微硬点的

看着就好吃，尤其喜欢这里面的土豆，入口即化吧？
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

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

: 看着就好吃，尤其喜欢这里面的土豆，入口即化吧？

v*72011-12-16 08:12

21 楼

对，如果heap用binary tree来表示，那么需要有parent指针的信息，in place可以做
，我这里刚
才想了一个算法，是O(nlgn)的做法，可以做到。
我在想用array表示的heap转换成array 表示的BST要怎么做。

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

: 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
: 所以operation仍然是O(logN).
: 对于用array表示的heap和BST, 怎么样来转换呢？

v*72011-12-16 08:12

22 楼

Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
到parent
指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。

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

: 这个链接是二叉树的链接法，就是node有left child, right child, parent指针。
: 所以operation仍然是O(logN).
: 对于用array表示的heap和BST, 怎么样来转换呢？

f*z2011-12-16 08:12

23 楼

分享一下算法吧

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

:
: Sorry，呵呵，刚明白过来，要是用array表示的heap，那做起来更简单，因为不需要用
: 到parent
: 指针了，其他都一样，那么time complexity还是O(nlgn),也是inplace的。

t*02011-12-16 08:12

24 楼

do you have to call
getMin n times to get the linked list?
that is nlgn
I think it does not matter if pointer or array is used to represent the
heap right?

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

: min heap->linkedlist->BST
:
: structure and

t*02011-12-16 08:12

25 楼

this is more like
heap -> sorted array -> bst

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

: do you have to call
: getMin n times to get the linked list?
: that is nlgn
: I think it does not matter if pointer or array is used to represent the
: heap right?

S*n2011-12-16 08:12

26 楼

you mean you can use array to represent bst?

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

: this is more like
: heap -> sorted array -> bst

b*s2011-12-16 08:12

27 楼

heap sorting O(nlogn)
然后就可以说这是BST了
root是n/2的点
左child是 n/4 ,右child是3n/4
一路二分下去
仅仅是各层节点没有按顺序存放而已

f*42011-12-16 08:12

28 楼

heap sort需要额外空间吧？

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

: heap sorting O(nlogn)
: 然后就可以说这是BST了
: root是n/2的点
: 左child是 n/4 ,右child是3n/4
: 一路二分下去
: 仅仅是各层节点没有按顺序存放而已

f*42011-12-16 08:12

29 楼

如果是用array，排序后，怎么不用额外空间构建BST？

C*y2011-12-16 08:12

30 楼

why not quick sort on the heap?
这样的话还是O(nlogn),但是不需要额外空间
———————————————————
俺错了，heap sort是O（1）的空间

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

: heap sorting O(nlogn)
: 然后就可以说这是BST了
: root是n/2的点
: 左child是 n/4 ,右child是3n/4
: 一路二分下去
: 仅仅是各层节点没有按顺序存放而已

f*42011-12-16 08:12

31 楼

对但是sort后怎么倒腾成表示bst的array？
比如
1 2 3 4 5 6 7
变成
4 2 6 1 3 5 7
？

【在 C***y 的大作中提到】

: why not quick sort on the heap?
: 这样的话还是O(nlogn),但是不需要额外空间
: ———————————————————
: 俺错了，heap sort是O（1）的空间

C*y2011-12-16 08:12

32 楼

你就可以当它是bst
4是root，2是左子树的root，6是右子树的root。。。。
不知道有没有这么表示的

【在 f*******4 的大作中提到】

: 对但是sort后怎么倒腾成表示bst的array？
: 比如
: 1 2 3 4 5 6 7
: 变成
: 4 2 6 1 3 5 7
: ？

f*42011-12-16 08:12

33 楼

不能吧。。。。

【在 C***y 的大作中提到】

: 你就可以当它是bst
: 4是root，2是左子树的root，6是右子树的root。。。。
: 不知道有没有这么表示的

t*02011-12-16 08:12

34 楼

Yes -
The result of heapsort is a sorted array (no need of extra space)
and bst can be represented by array
http://discuss.joelonsoftware.com/default.asp?interview.11.6646
is this an efficient representation...

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

: you mean you can use array to represent bst?

z*e2011-12-16 08:12

35 楼

我觉得，基本上意思是把每次sort后的结果，提出root（middle value）来，然后对左
右sub tree调整后recursive地反复找root.关键在于对left/right tree的调整。
1
2 3
4 5 6 7
step 1: 交换a[0]和a[middle],也就是a[0]和a[3]交换变成 4 2 3 1 5 6 7
4
2 3
1 5 6 7
注意到 a[middle+1...n/2+1]（left tree在middle value之后的所有siblings）都>
root，同时right tree中a[n/2+2]之前的都小于root，所以要对换value变成
4
2 5
1 3 6 7
（你用一个较大的array比如1 2 3 ....15，比较容易看出来）
然后对left/right各自repeat上述步骤。

【在 f*******4 的大作中提到】

: 对但是sort后怎么倒腾成表示bst的array？
: 比如
: 1 2 3 4 5 6 7
: 变成
: 4 2 6 1 3 5 7
: ？