一道《编程之美》第一章的无解题引发的“血案”

今天在一堂无聊的课上看《编程之美》，一口气看完了第一章，其中有两个一笔带过的题目，在后面的内容中暂时也没有看到解法，引起了我极大的兴趣23333，太过好玩于是打算写个博客记录一下。

此次博客中提到的两个问题都仅是初读第一章后印象最深的比较好玩的游戏，之后精读的时候打算把没有给出答案的题目都做做看。
包括那个烙饼，我真想不明白书上的代码怎么会那那那么长！（想完之后再翻阅代码发现竟然占了三四页就没有细看orz）我觉得c++50行能解决，思路是先sort把所有数字从大到小降序排序O(nlogn），然后for这个数组遍历去找第 i 大烙饼，如果是用链表存储，那么查找O(n)翻转O(1)，这样做复杂度是O(n^2)。

后来看到了其他博主关于部分题解的整理，先mark：精选的一些《编程之美》相关资料

puzzle1：回环链表

题面：如何判断一个链表存在环路？
（在书里只是提了下说一个已面试结束的人出去向别人透了这题，然后另一位面试时佯装思索然后背诵答案2333）

这道题我曾经在LeetCode见过，我的解法是：

一、如果链表节点可自定义，那么增设一个布尔值的 isVisitied 变量，初始化为0，遍历后置为1，当某次遍历到一个该变量为1的节点时，说明回环了
二、如果链表长度已知为n，遍历到第n个节点时，发现其 next 指针不为空则回环了

这道题在LeetCode的discuss中票数最高的解法是：

定义一个 walker 指针和一个 runner 指针，一开始都指向链表的头节点，开始遍历： walker = walker->next;（walker步长为1），runner = runner->next->next;（runner步长为2），当发现它们相遇的时候说明回环了。

可以证明这种做法的正确性，也即证明存在一个m使得满足：m%N == 2*m%N，显然当 m=N 的时候成立。

puzzle2：房间里的灯

题面：房间里有三盏灯，外有三个开关，怎么做到只进入房间一次，却能够知道哪个开关控制的是哪个灯？

解法一改造开关法

开始看到这题目，想了一会感觉不太对劲啊，这能解吗？？无论如何在房间外开几盏灯，进去后都是最多只能判断出一盏，因为怎么开都总会有两盏的状态是完全一样的。除非某一开关能增设定时装置，能让人进去之后再自动开启。

解法二第三状态法

百思不得其解，于是把题目发给了一个能动专业的好友，得到如下解答：

在房间外面疯狂地反复快速翻转开关，利用启动瞬间高电压尝试击穿一个灯的电容/烧坏一个灯的灯丝。然后从容地闭合另外一个开关，进入房间。

我惊了！作为标准程序员一看到开关已经是满脑子的只有0、1两种状态，原来还能自己构造第三种状态的吗！23333

然后在脑洞爆炸模式下，另有以下各种解法：

解法三瞬间移动法

在间隔极短的时间内打开两盏灯，然后在两盏灯先后亮起的中间节点瞬移到房间内。

解法四带走开关法

将原开关拆开，用另外三个开关分别并联原开关，然后把另外三个开关（如果不是无线那么还要带着导线）带到房间里面

解法五指鹿为马法

根据主观唯心主义，任意决定一个开关-灯配对，然后把不同意这个答案的人都干掉

233333我简直迫不及待的想知道这道面试题在出题方最终的合理解法是什么了！