反功利主义，Interstellar关于地球的部分，很有意思 - 未名空间MITBBS历史存档

反功利主义，Interstellar关于地球的部分，很有意思# Movie - 无限影话

r*o2014-11-18 08:11

1 楼

刚才看到有人的面经里面有这个题目。
有谁有什么好办法吗？
我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
这个方法时间复杂度和空间复杂度都是O(n),
有谁有更好的方法吗？

l*a2014-11-18 08:11

2 楼

有人觉得前半段关于地球末日的部分太冗长，我个人觉得没有。
首先，大多数科幻作品对末日的描写都要惊悚多得多——啥核战啦，AI take over 啦
，外星人入侵啊，僵尸啊，病毒啊，地球坍塌变冷变热啊，地震海啸啦，月球爆炸或
者外天体砸下来啦。。。Interstellar里，反其道而行之，地球的毁灭的罪魁祸首无
非是沙尘暴，因而造成的食物短缺，空气缺氧 —— 人类会死于这样很慢却又很无奈的
死法。。。。这种"朴素"到令人发指的死法（要不要这么低调啊~~~）的设定非常大
胆，其实也是从另一个方向契合了 whatever can happen will happen 的主题，非常
有新意。
另外一个有趣的地方，一般描写末日的社会，一般总认为人类会全力发展科技最后一搏
，绝大多数的科幻片里的描写也确实是这样的。至少得像《后天》那样造个十个八个巨
型高科技方舟吧。interstellar里没有，令人意外的，人类放弃了在科技的投入，而选
择最功利最实际的“低科技”化，全民务农，宇航员也不例外。课本被改写成“正确”
（注意：不是“真实”，correct这个词快被玩坏了。）的版本，从而从根子上扼杀一
切对梦想的追逐。
如Cooper所言: We used to look up at the sky and wonder at our place in the
stars, now we just look down and worry about our place in the dirt. 这段描
写也很有新意，很讽刺，很实际（看看天朝历史就不难理解这种倾向了。。。这种寓
言式的描写让我联想起《Animal Farm》和《1984》。要不要这么损天朝啊，诺神，连
沙尘暴也是损俺们吧。。。）
人类的功利主意在短期内也许能带来暂时的利益最大化，但从长期来看，会像水煮青蛙
般的走向灭亡。人类在文化艺术科技方面的追求永远应该是非功利的。
=====================================================
这种反功利主义的思路也延续到电影的后半段—— plan B 相对于 plan A，就是极其
功利的。plan B 用最小的损失（在得到前期反馈以后，只要宇宙飞行器1艘+宇航员3-
4名， N多人类受精卵）就完全能达到人类续香火的目的了。 plan A先要解些方程，还
从 black hole's singularity收集数据，然后制造反动力专制，从地球集体迁徙。。
。和plan B比起来
，典型的夸父逐日，很傻很无望。。。
不过真的是这样么？至少自Cooper看来(当然如果cooper想错了，五维人就是另外一回
事了），五维人是人类的后裔，从高维发动干涉给他机会去实施plan A。也许“五维人
” 本身是plan A发展出的后裔，当然也可能是plan B留下的香火.... 这个ambiguity
我觉得设置得挺有趣的，因为怎么想都行，哪种可能性都很有意思。
=====================================================
最后，电影讲的也许并不（只）是“爱拯救世界”的故事。更多，是理性和非理性（
也包括功利vs非功利）的冲突。就好像人类在象棋上能战胜比自己计算超前N步的计算
机，人类的"人性元素"（比如：爱，求生欲，恐惧，创造力。。。）不稳定，不理性，
没道理。但是，很执着。偶尔的，还有洞穿一切理性的力量。毕竟理性的东西都是建立
在目前有限knowledge之上，而非理性的东西，有时反而能打破这种界限。
[[诺神弟对人性元素的青睐由来已久，参见他写滴电视剧POI——神级AI一样要有人的
监护]]
=======================================================================
p.s. 我也很喜欢gravity（2013），gravity入口很小，却切入很深。interstellar开
口很大，气势磅礴，层层嵌套，同样有很深的看点，确实可以看出来是奔着 2001： a
space odyssey （1968）那高度去的。

f*e2014-11-18 08:11

3 楼

跟找环算法一样，只是再往前推进一个节点

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

: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？

j*x2014-11-18 08:11

4 楼

哎神经病人欢乐多啊

r*o2014-11-18 08:11

5 楼

找环算法怎么返回环的位置?

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

: 跟找环算法一样，只是再往前推进一个节点

l*a2014-11-18 08:11

6 楼

你的回帖正说明：我们完全不是一路人，非常好。
有幸有幸~~~~~

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

: 哎神经病人欢乐多啊

f*e2014-11-18 08:11

7 楼

你用的是哪个找环算法

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

: 找环算法怎么返回环的位置?

u*t2014-11-18 08:11

8 楼

主角放个屁也能引起lz自恨？药不能停啊。

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

: 有人觉得前半段关于地球末日的部分太冗长，我个人觉得没有。
: 首先，大多数科幻作品对末日的描写都要惊悚多得多——啥核战啦，AI take over 啦
: ，外星人入侵啊，僵尸啊，病毒啊，地球坍塌变冷变热啊，地震海啸啦，月球爆炸或
: 者外天体砸下来啦。。。Interstellar里，反其道而行之，地球的毁灭的罪魁祸首无
: 非是沙尘暴，因而造成的食物短缺，空气缺氧 —— 人类会死于这样很慢却又很无奈的
: 死法。。。。这种"朴素"到令人发指的死法（要不要这么低调啊~~~）的设定非常大
: 胆，其实也是从另一个方向契合了 whatever can happen will happen 的主题，非常
: 有新意。
: 另外一个有趣的地方，一般描写末日的社会，一般总认为人类会全力发展科技最后一搏
: ，绝大多数的科幻片里的描写也确实是这样的。至少得像《后天》那样造个十个八个巨

r*o2014-11-18 08:11

9 楼

你说你用的哪一种吧，我这里没有找环，不过单链表反转可以用来找环。

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

: 你用的是哪个找环算法

h*v2014-11-18 08:11

10 楼

特别赞同！

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

: 有人觉得前半段关于地球末日的部分太冗长，我个人觉得没有。
: 首先，大多数科幻作品对末日的描写都要惊悚多得多——啥核战啦，AI take over 啦
: ，外星人入侵啊，僵尸啊，病毒啊，地球坍塌变冷变热啊，地震海啸啦，月球爆炸或
: 者外天体砸下来啦。。。Interstellar里，反其道而行之，地球的毁灭的罪魁祸首无
: 非是沙尘暴，因而造成的食物短缺，空气缺氧 —— 人类会死于这样很慢却又很无奈的
: 死法。。。。这种"朴素"到令人发指的死法（要不要这么低调啊~~~）的设定非常大
: 胆，其实也是从另一个方向契合了 whatever can happen will happen 的主题，非常
: 有新意。
: 另外一个有趣的地方，一般描写末日的社会，一般总认为人类会全力发展科技最后一搏
: ，绝大多数的科幻片里的描写也确实是这样的。至少得像《后天》那样造个十个八个巨

f*e2014-11-18 08:11

11 楼

两个指针，一个跨一步，一个跨两步，当相交时就是环的"尾巴"

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

: 你说你用的哪一种吧，我这里没有找环，不过单链表反转可以用来找环。

h*v2014-11-18 08:11

12 楼

延伸一下，人类因为爱而延续，我觉得导演有这个信念

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

: 有人觉得前半段关于地球末日的部分太冗长，我个人觉得没有。
: 首先，大多数科幻作品对末日的描写都要惊悚多得多——啥核战啦，AI take over 啦
: ，外星人入侵啊，僵尸啊，病毒啊，地球坍塌变冷变热啊，地震海啸啦，月球爆炸或
: 者外天体砸下来啦。。。Interstellar里，反其道而行之，地球的毁灭的罪魁祸首无
: 非是沙尘暴，因而造成的食物短缺，空气缺氧 —— 人类会死于这样很慢却又很无奈的
: 死法。。。。这种"朴素"到令人发指的死法（要不要这么低调啊~~~）的设定非常大
: 胆，其实也是从另一个方向契合了 whatever can happen will happen 的主题，非常
: 有新意。
: 另外一个有趣的地方，一般描写末日的社会，一般总认为人类会全力发展科技最后一搏
: ，绝大多数的科幻片里的描写也确实是这样的。至少得像《后天》那样造个十个八个巨

r*o2014-11-18 08:11

13 楼

你这个环的尾巴是怎么定义的？
假定一个单链表,1->2->3->4->5->6->7 7又指向5
fast: 1->3->5->7->6->5->7->6...
slow: 1->2->3->4->5->6->7->5...
两者在7相遇，
再假定一个单链表,1->2->3->4->5->6->7->8 8又指向5
fast: 1->3->5->7->5->7->5->7...
slow: 1->2->3->4->5->6->7->8...
两者在5相遇，
这两者相遇的地方没规律。
在 feelalone (感到孤独) 的大作中提到: 】

l*a2014-11-18 08:11

14 楼

是啊，诺神的电影，虽然都是男主s老婆，但往往蕴含一个闷骚的爱情故事。。。

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

: 延伸一下，人类因为爱而延续，我觉得导演有这个信念

f*e2014-11-18 08:11

15 楼

看来我搞错了，还得再研究下
感觉应该是这个思路吧？

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

: 你这个环的尾巴是怎么定义的？
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7->6...
: slow: 1->2->3->4->5->6->7->5...
: 两者在7相遇，
: 再假定一个单链表,1->2->3->4->5->6->7->8 8又指向5
: fast: 1->3->5->7->5->7->5->7...
: slow: 1->2->3->4->5->6->7->8...
: 两者在5相遇，
: 这两者相遇的地方没规律。

z*y2014-11-18 08:11

16 楼

写得挺好.

f*42014-11-18 08:11

17 楼

找环的算法后面还有一部分
当fast和slow相遇之后
fast remove到head，然后每次 move 1 step，当fast和slow再次相遇就是环的开始节
点。得到这个节点N，你再遍历一下list，如果当前节

l*l2014-11-18 08:11

18 楼

主角配角还有楼主，都爱爱爱个不停。有点无病呻吟哦。不就一科幻么，关爱个屁事啊
？

r*o2014-11-18 08:11

19 楼

多谢。
但是如果fast指针后来也每次move 1 step，那就跟slow 指针速度一样了。
感觉这样的话，有可能两个指针慢悠悠的转圈，但是就是不相遇啊。

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

: 找环的算法后面还有一部分
: 当fast和slow相遇之后
: fast remove到head，然后每次 move 1 step，当fast和slow再次相遇就是环的开始节
: 点。得到这个节点N，你再遍历一下list，如果当前节

Z*72014-11-18 08:11

20 楼

前面都看睡着了

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

: 有人觉得前半段关于地球末日的部分太冗长，我个人觉得没有。
: 首先，大多数科幻作品对末日的描写都要惊悚多得多——啥核战啦，AI take over 啦
: ，外星人入侵啊，僵尸啊，病毒啊，地球坍塌变冷变热啊，地震海啸啦，月球爆炸或
: 者外天体砸下来啦。。。Interstellar里，反其道而行之，地球的毁灭的罪魁祸首无
: 非是沙尘暴，因而造成的食物短缺，空气缺氧 —— 人类会死于这样很慢却又很无奈的
: 死法。。。。这种"朴素"到令人发指的死法（要不要这么低调啊~~~）的设定非常大
: 胆，其实也是从另一个方向契合了 whatever can happen will happen 的主题，非常
: 有新意。
: 另外一个有趣的地方，一般描写末日的社会，一般总认为人类会全力发展科技最后一搏
: ，绝大多数的科幻片里的描写也确实是这样的。至少得像《后天》那样造个十个八个巨

f*42014-11-18 08:11

21 楼

fast remove到list head
你google一下吧，可以证明他们相遇点是环开始的

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

: 多谢。
: 但是如果fast指针后来也每次move 1 step，那就跟slow 指针速度一样了。
: 感觉这样的话，有可能两个指针慢悠悠的转圈，但是就是不相遇啊。

j*x2014-11-18 08:11

22 楼

我可不是神经病~~~

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

: 你的回帖正说明：我们完全不是一路人，非常好。
: 有幸有幸~~~~~

r*o2014-11-18 08:11

23 楼

奇怪，看看这个例子，
假定一个单链表,1->2->3->4->5->6->7 7又指向5
fast: 1->3->5->7->6->5->7
slow: 1->2->3->4->5->6->7
两者在7相遇，
相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
fast: 1->2->3->4->5->6->7...
slow: 5->6->7->5->6->7->5...
好像永远都不会相遇啊。是不是我哪儿理解得不对?

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

: fast remove到list head
: 你google一下吧，可以证明他们相遇点是环开始的

k*e2014-11-18 08:11

24 楼

狂顶lemma！非常赞。

f*e2014-11-18 08:11

25 楼

在7相遇
fast: 7 5 6 7 5 6 7
slow: 1 2 3 4 5 6 7

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

: 奇怪，看看这个例子，
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7
: slow: 1->2->3->4->5->6->7
: 两者在7相遇，
: 相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
: fast: 1->2->3->4->5->6->7...
: slow: 5->6->7->5->6->7->5...
: 好像永远都不会相遇啊。是不是我哪儿理解得不对?

s*m2014-11-18 08:11

26 楼

鈮筇焘壂里没有高科技方舟，谢谢。

H*X2014-11-18 08:11

27 楼

我记得有个数学推导，相遇之后，能算出来环从哪开始的

l*a2014-11-18 08:11

28 楼

：P 记错了，2012里的。。。 >_< ||| 谢谢更正。

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

: 鈮筇焘壂里没有高科技方舟，谢谢。

y*i2014-11-18 08:11

29 楼

我有一个idea，你看行不行？
当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
要的结果了。这个方法也同样适用于找环的初始结点。

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

: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？

r*o2014-11-18 08:11

30 楼

这个方法不错，多谢。

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

: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。

y*i2014-11-18 08:11

31 楼

不客气，互相交流，共同进步！

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

: 这个方法不错，多谢。

f*42014-11-18 08:11

32 楼

slow 7->5->6->7->5->6->7
slow没有动
这个方法用来找到环开始的节点，可以用来解变体
找到环中第m个节点

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

: 奇怪，看看这个例子，
: 假定一个单链表,1->2->3->4->5->6->7 7又指向5
: fast: 1->3->5->7->6->5->7
: slow: 1->2->3->4->5->6->7
: 两者在7相遇，
: 相遇后fast move 到head, 然后两个指针一起慢跑，每次step 1
: fast: 1->2->3->4->5->6->7...
: slow: 5->6->7->5->6->7->5...
: 好像永远都不会相遇啊。是不是我哪儿理解得不对?

d*d2014-11-18 08:11

33 楼

先找到环的起点,然后从头再来,第一次出现p->next==环起点的时候即可。

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

: 刚才看到有人的面经里面有这个题目。
: 有谁有什么好办法吗？
: 我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
: 以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
: 这个方法时间复杂度和空间复杂度都是O(n),
: 有谁有更好的方法吗？

s*92014-11-18 08:11

34 楼

怎么找这个交点呢？

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

: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。

m*g2014-11-18 08:11

35 楼

assume when fast meet slow for the first time, slow has travelled D+L, fast
has travelled D+L+kS
D is from list head to the beginning of loop, L is from beginning of loop to
this position, which is a portion of the loop length, k is any positive int
, S is loop length.
since the time was same, we have (D+L)/1 = (D+L+kS)/2
we get D = kS-L = (k-1) S + (S-L)
So if we let another ptr (fast) to start from head with same speed as slow,
when it travels D, the slow would have travelled (k-1)S + (S-L), w

j*l2014-11-18 08:11

36 楼

这个CareerCup的150题收录了，解答比较清楚

m*g2014-11-18 08:11

37 楼

咋搞这复杂咛? 为啥弄俩小破恩特追着玩?
没空间要求的话. 整个list中, 只有一个地址被用了两次, 就是环的起点. 线性遍历把
地址(reference)扔hash里 O(1), 冲突了就找到了. total O(n)
这样处理有啥毛病么?

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

: 我有一个idea，你看行不行？
: 当快慢两个指针相遇时，把环从这里打开，让相遇结点作为另一个list的head，相遇前
: 的结点指向NULL。这样问题就又变成了两个lists找相交点的问题了，原来的head的那
: 个list的相交点的前一个结点就是你要的了。特殊情况：如果快慢两个指针在环的初始
: 结点相遇，那么这样做的结果就会导致另一个list又变成了一个环（可以用快慢指针事
: 先做一下这个判断），而原来的list跟这个环list没有相交，那么也很容易就能找出你
: 要的结果了。这个方法也同样适用于找环的初始结点。

y*i2014-11-18 08:11

38 楼

没啥毛病，hacking a google interview中我记得讲过，有的面试官喜欢hash，有的
hate hash，如果你正好碰上了后者，那是不是还要准备另一种解法？

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

: 咋搞这复杂咛? 为啥弄俩小破恩特追着玩?
: 没空间要求的话. 整个list中, 只有一个地址被用了两次, 就是环的起点. 线性遍历把
: 地址(reference)扔hash里 O(1), 冲突了就找到了. total O(n)
: 这样处理有啥毛病么?