我和按摩女的故事——（二）初见 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Love - 情爱幽幽

我和按摩女的故事——（二）初见 (转载)

我和按摩女的故事——（二）初见 (转载)# Love - 情爱幽幽

A*r2013-12-17 08:12

1 楼

topcoder上有关于LCA的算法，比较能够接受的有两个：
1）用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
（详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor）
不过看到了careercup上给出的一个非DP算法，recursive的，貌似算法复杂度也只有O(
n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
但在实际面试题中，我们一般都是会给定两个node，这样看来careercup上的不是更好
吗？！
下面给出careercup上的算法，大家讨论一下看看。
/* Returns NULL, p, q or the nearest common ancestor of p and q, assume p
and q are in the tree

O*12013-12-17 08:12

2 楼

【以下文字转载自 RuralChina 讨论区】
发信人: OckhamT1 (奥卡姆剃刀), 信区: RuralChina
标题: 我和按摩女的故事——（二）初见
发信站: BBS 未名空间站 (Tue Dec 17 17:57:01 2013, 美东)
我们可能是世界上最讲究“名”的一个民族，一些成语诸如“师出有名”“名正言顺”
“名至实归”都反映了这种讲究“名”的文化，而这种文化本质上就是我们这个民族所
特有的“面子文化”。比如“按摩”听起来就不如“指压”高端，再比如“餐馆”感觉
上就不如“料理”讲究，而把“生物化学学院”改成“生命科学学院”就显得更加大气
上档次了，这也许就是我们学院改名字的初衷吧。
胡思乱想间，我就走进了这所新开的日式指压店。这家店有三层，一进门是一个大厅，
大厅前台后面站着一位短发的姑娘。
“先生您好，请问您需要什么服务？”短发姑娘一口标准的普通话。
“哦，做个局部吧，主要是肩膀和后背”，这些天的招聘会还真是累人，肩周疼的老毛
病又犯了。
“先生，我们店近期有优惠活动，全身+足底一共才168元，您如果只做局部的话也要
120元，不合适。我建议您选择套餐”，姑娘很耐心的推销着他们的“套餐服务”。
面对这种推销技巧我确实无计可施，总不能在一个小姑娘面前为了区区40几块钱掉面子
吧。
“好，听你的”。这40多元钱的服务升级居然让我一时间有了一种成功者的感觉，说话
的语气也显得多了几分自信。
随后一个年轻小伙子领着我去了一个鞋柜前，换上了一次性拖鞋。
“先生，您需要擦鞋吗？”小伙子帮我拿鞋的时候问。
“好的”，我随手递给他10块钱小费。
“先生，我们不收小费的，最后一起结算，擦皮鞋收费20元。”
“哦，这样啊......”，我显得有些尴尬。
这个小伙把我领到了一个房间，房门上嵌着两个金色的字母“QQ”，我这才注意到这里
的房门号是重叠的英文字母，“AA”，“BB”......
“先生请稍候，技师很快就来为您服务。”说完小伙就离开了。
房间不大，只有一张按摩床和一个小沙发，墙上还挂着一幅画，很常见的一幅画，一个
半裸的年轻姑娘在右胸前双手抱着一个瓦罐，姿态端庄，表情严肃，背后是大海和一个
小岛。
不一会儿，一个女孩推门进来，手里提着一个小篮子，身上穿着大概是这家店的制服，
粉色上衣粉色一步裙肉色丝袜，一双浅色小短靴。往脸上看，清纯的脸庞上无半点脂粉
，白里透红散发着诱人的青春气息，眉清目秀，雅致的鼻子，小巧的嘴，居然和画里的
姑娘有几分相似。
“先生您好，36号技师为您服务。先给您倒杯水吧，您是要热的还是凉的？”女孩的话
语让我意识到刚才看她看的有些失态。
“哦，谢谢，不用了”，我居然有些局促起来。
不一会儿，她就准备好了足浴的盆，往里面添加了热水和一些中药材，又从小篮子里拿
出了毛巾和按摩膏。
让这么可人的小姑娘帮我洗脚，更感觉有些不好意思了。姑娘双手在我膝盖和大腿上揉
了揉，又帮我撸起裤管，甜甜的冲我笑了笑，“放松，不是打针，不用害怕”。
姑娘一边熟练的按着我脚底的穴位，一边和我聊天。
“先生您在哪行发财啊？”
“你看我像做什么的。”
“看您这么儒雅有气质，是大学老师吧？”
“呵，厉害啊，一猜就中”。
“不瞒你说，我弟弟今年刚上大学，真希望他将来和您一样成为一名大学老师。”
“哦？你弟弟考上哪了？”
“田野大学，学生命科学呢，据说是21世纪最好的专业！”说到“21世纪最好的专业”
的时候，小姑娘一脸的自豪。
“瓜瓜打小就聪明，认识他的人都说他是念书的好料子。”小姑娘继续骄傲的夸着自己
的弟弟。
“哦，你弟弟叫瓜瓜啊？”我突然意识到她弟弟居然是我们院今年招的新生。
“呵呵，你以为是小名吧，其实是大名，我弟就叫瓜瓜。”
“你弟叫瓜瓜，那你叫什么名字啊？”
“哈哈，我叫豆芽菜！”

h*62013-12-17 08:12

3 楼

以前曾经想过一个方法，先序中序后序遍历二叉树。那么在先序的两个结点之前，中序
的两个结点之中，后序的两个结点之后，一定有一个唯一重复的结点，就是其最低公共
父结点。

Q*Q2013-12-17 08:12

4 楼

这一章好熟悉的感觉啊难道所有按摩脚的地方都一个流水线的么

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

: 【以下文字转载自 RuralChina 讨论区】
: 发信人: OckhamT1 (奥卡姆剃刀), 信区: RuralChina
: 标题: 我和按摩女的故事——（二）初见
: 发信站: BBS 未名空间站 (Tue Dec 17 17:57:01 2013, 美东)
: 我们可能是世界上最讲究“名”的一个民族，一些成语诸如“师出有名”“名正言顺”
: “名至实归”都反映了这种讲究“名”的文化，而这种文化本质上就是我们这个民族所
: 特有的“面子文化”。比如“按摩”听起来就不如“指压”高端，再比如“餐馆”感觉
: 上就不如“料理”讲究，而把“生物化学学院”改成“生命科学学院”就显得更加大气
: 上档次了，这也许就是我们学院改名字的初衷吧。
: 胡思乱想间，我就走进了这所新开的日式指压店。这家店有三层，一进门是一个大厅，

D*h2013-12-17 08:12

5 楼

递归栈你不算空间开销了?
topcoder上讨论的RMQ是可以在任意tree上查找LCA的。

O(
LCA,

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

: topcoder上有关于LCA的算法，比较能够接受的有两个：
: 1）用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
: 2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
: （详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor）
: 不过看到了careercup上给出的一个非DP算法，recursive的，貌似算法复杂度也只有O(
: n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
: 但在实际面试题中，我们一般都是会给定两个node，这样看来careercup上的不是更好
: 吗？！
: 下面给出careercup上的算法，大家讨论一下看看。
: /* Returns NULL, p, q or the nearest common ancestor of p and q, assume p

w*n2013-12-17 08:12

6 楼

你看他是不是很有经验？

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

: 这一章好熟悉的感觉啊难道所有按摩脚的地方都一个流水线的么

A*r2013-12-17 08:12

7 楼

我知道topcoder上的更general, 我只是说对于这个类型的面试题，有没有更容易直观
的算法。。
我指的空间，是一般面试题中说的需要额外保存的数据结构。

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

: 递归栈你不算空间开销了?
: topcoder上讨论的RMQ是可以在任意tree上查找LCA的。
:
: O(
: LCA,

A*r2013-12-17 08:12

8 楼

好像也可行，不过比较每个的path，最直接的方法估计要O(n*n)的时间吧。。

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

: 以前曾经想过一个方法，先序中序后序遍历二叉树。那么在先序的两个结点之前，中序
: 的两个结点之中，后序的两个结点之后，一定有一个唯一重复的结点，就是其最低公共
: 父结点。