2022-04-28 13:51 已编辑西北工业大学后端

关注

【总结】面试中常见的智力题

个人微信公众号【LifelongCode】，有问题可以直接提问哦😀😀

本文目录：

1. 二进制问题

1.1 毒药问题
1.2 分金块问题

2. 先手必胜问题

2.1 抢 30的必胜策略
2.2 100本书，每次能够拿1~5本，怎么拿能保证最后一次是你拿？
2.3 轮流拿石子

3. 推理题

3.1 掰巧克力问题
3.2 辩论赛问题
3.3 在24小时里面时针分针秒针可以重合几次
3.4 N只蚂蚁走树枝，问总距离或者总时间
3.5 旅馆的1元钱问题

4. 概率问题

4.1 家里有两个孩子，一个是女孩，另一个也是女孩的概率是多少？
4.2 一条绳子砍两刀，能构成一个三角形的概率？
4.3 一个圆上随机画两条弦，求相交的概率？
4.4 犯人猜颜色
4.5 火枪手决斗，谁活下来的概率大？

5. 水桶问题

5.1 水资源无限，3L和5L水桶各一个，怎样取4L的水？
5.2 水资源无限，5L和6L水桶各一个，怎样取3L的水？
5.3 一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？
5.4 舀酒问题：只有两个舀酒的勺子，分别能舀7两和11两酒，如何舀出2两酒？

6. 计时问题

6.1 有一个能计时6分钟的小沙漏和一个能计时8分钟的大沙漏，如何计时10分钟？
6.2 烧一根绳子需要一个小时，现有若干条相同的绳子，问如何计时15分钟？
6.3 蜡烛燃烧问题：两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？

7. 赛马问题

7.1 25匹马5条跑道找最快的3匹马，需要跑几次？
7.2 64匹马8条跑道找最快的4匹马，需要跑几次？
7.3 25匹马5条跑道找最快的5匹马，需要跑几次？

8. 过河/过桥问题

8.1 三人三鬼过桥
8.2 限时过桥问题

9. 最优解问题

9.1 猴子搬香蕉
9.2 高楼扔鸡蛋
9.3 利用空瓶换饮料，最多喝几瓶

10. 数字问题

10.1 11***44问题
10.2 给定随机函数，生成别的随机数

11. 重量问题

11.1 乒乓球重量问题：8个乒乓球，其中一个重，有一个秤，问至少几次能够找出重的那个乒乓球
11.2 盐重量问题：有7克、2克砝码各一个，天平一只，如何只用这些物品五次内将140克的盐分成50、90克各一份？
11.3 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？
11.4 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？
11.5 药丸问题：有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次；
11.6 药丸问题：你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了？

12. 灯泡开关问题

12.1 在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？
12.2一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮。

13. 蓝眼/疯狗/耳光问题

13.1 蓝眼睛问题
13.2 疯狗问题
13.3 耳光问题

1. 二进制问题

1.1 毒药问题

问题：有1000个一模一样的瓶子，其中有999瓶是普通的水，有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间，如何检验出哪个瓶子有毒药？

首先一共有1000瓶，2的10次方是1024，刚好大于1000，也就是说，1000瓶药品可以使用10位二进制数就可以表示。

从第一个开始：

第一瓶： 00 0000 0001
第二瓶： 00 0000 0010
第三瓶： 00 0000 0011
……
第999瓶： 11 1111 0010
第1000瓶：11 1111 0011

需要十只老鼠，如果按顺序编号，ABCDEFGHIJ分别代表从低位到高位每一个位。每只老鼠对应一个二进制位，如果该位上的数字为1，则给老鼠喝瓶里的药。观察，若死亡的老鼠编号为：ACFGJ，一共死去五只老鼠，则对应的编号为 10 0110 0101，则有毒的药品为该编号的药品，转为十进制数为：613号。

1.2 分金块问题

问题：工人为老板打工，工作七天可以获得一块金子，工人每天可以分得一点金子，老板必须每天发金子，不能多给，也不能少给，把这个金子切两刀，就可以每天给工人发工资，请问怎么切？

切两刀将金子分成三份，1/7、2/7、4/7；

工作第一天把1/7分给工人；
工作第二天把2/7分给工人，并要回1/7那块金子，工人有2/7的金子；
工作第三天把1/7给工人工人有3/7金子；
工作第四天把前两块金子要回，给工人4/7的金子工人有4/7的金子；
工作第五天把1/7分给工人工人有5/7的金子；
工作第六天把2/7分给工人，并要回1/7那块金子，工人有6/7的金子；
工作第七天把1/7给工人工人有完整的金子；

扩展：如何给工人发15天的工资？把金块分成1/15、2/15、4/15、8/15。

2. 先手必胜问题

2.1 抢 30的必胜策略

问题：抢 30 是双人游戏，游戏规则是：第一个人喊“ 1 ”或“ 2 ”，第二个人要接着往下喊一个或两个数，然后再轮到第一个人。两人轮流进行下去，最后喊 30 的人获胜，问喊数字的最佳策略。

尽量喊3的倍数；

解析：倒着看，其实，喊 27 时，就决定胜负了。

假设 A 喊了 27，B只能喊 28 或 29 ，下个回合，A 一定可以喊30。也就是说，喊 27 者必胜。

再倒着看，其实喊 24 时，就定胜负了。假设 A 喊了 24 ，B 只能喊 25 或 26 ，下个回合 A 一定能喊 27 。

由于喊 27 者必胜，因此喊 24 者也必胜。

同理可以推出：喊 3 的倍数者必胜。

然后就会发现，这个游戏，谁先喊，谁一定输

2.2 100本书，每次能够拿1~5本，怎么拿能保证最后一次是你拿？

如果最后一次是我拿，那么上回合最少剩下6本；

只要保持每个回合结束后都剩下6的倍数，且在这个回合中我拿的书和对方拿的书加起来为6本；

第一次我必须先手拿4本(100 % 6 = 4)，这不算在第一回合内。

2.3 轮流拿石子

问题1：一共有N颗石子（或者其他乱七八糟的东西），每次最多取M颗最少取1颗，A，B轮流取，谁最后会获胜？（假设他们每次都取最优解）。

答案：简单的巴什博奕：https://www.cnblogs.com/StrayWolf/p/5396427.html

问题2：有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。

答案：较复杂的尼姆博弈:https://blog.csdn.net/BBHHTT/article/details/80199541

3. 推理题

3.1 掰巧克力问题

问题：一块N * M大小的巧克力，每次掰一块的一行或一列，全部掰成 1 * 1 大小的巧克力需要掰多少次？

N * M - 1次；

不管怎么掰，每次只能把一个大块掰成两个小块，即每次掰只能增加1块巧克力；那么将1块巧克力掰成N * M块小巧克力就需要掰N * M - 1次。

3.2 辩论赛问题

问题：1000个人参加辩论赛，1对1进行辩论，淘汰输掉的一方，问需要安排多少场比赛才能角出冠军？

每场辩论赛只能淘汰一个人，要淘汰999个人则需要安排999场比赛。

3.3 在24小时里面时针分针秒针可以重合几次

24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次，而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次

3.4 N只蚂蚁走树枝，问总距离或者总时间

问题：放N只蚂蚁在一条长度为M树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间为多少？

参考回答：这个其实就一个诀窍：蚂蚁相碰就往反方向走，可以直接看做没有发生任何事：大家都相当于独立的，A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞，这样无论是求时间还是距离都很简单了。

3.5 旅馆的1元钱问题

问题：有三个人去住旅馆，住三间房，每一间房10元，于是他们一共付给老板30，第二天，老板觉得三间房只需要25元就够了于是叫小弟退回5给三位客人，谁知小弟贪心,只退回每人1，自己偷偷拿了2，这样一来便等于那三位客人每人各花了九元，于是三个人一共花了27，再加上小弟独吞了不2，总共是29。可是当初他们三个人一共付出30那么还有$1呢？

他们所消费的27元里已经包括小弟贪污的2元了，再加退还的3元=30元；这30元现在的分布是：老板拿25元，伙计拿2元，三人各拿1元，正好！

4. 概率问题

4.1 家里有两个孩子，一个是女孩，另一个也是女孩的概率是多少？

1/3

样本空间为（男男）（女女）（男女）（女男）

A＝（已知其中一个是女孩）＝（女女）（男女）（女男）

B＝（另一个也是女孩）＝（女女）

于是P（B／A）＝P（AB）／P（A）＝（1／4）／（3／4）＝1／3

4.2 一条绳子砍两刀，能构成一个三角形的概率？

设绳子总长为L，分成三段为：x，y，L - x - y；其中x > 0，y > 0， L - x - y > 0，取值范围如图中蓝***域所示；

又因为任意两边之和要大于第三边，故有如下条件： x + y > L - x - y => y > -x + L / 2； x + (L - x - y) > y => y < L / 2; y + (L - x - y) > x => x < L / 2;

该区域为图中绿***域，占蓝***域的四分之一；

4.3 一个圆上随机画两条弦，求相交的概率？

四个点确定两条线，在一个圆上取四个点；四个点画两条线有三种情况，其中只有一种情况是相交的，故相交概率为三分之一；

4.4 犯人猜颜色

问题：一百个犯人站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．然后从最后一个犯人开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的答案所有犯人都能听见，是否说对，其他犯人不知道，在这之前，所有犯人可以聚在一起商量策略，问如果犯人都足够聪明而且反应足够快，100个人最大存活率是多少？

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死

2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一

3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”

99人能100%存活，1人50%能活

4.5 火枪手决斗，谁活下来的概率大？

问题：彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

参考回答：一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大；

那么我们先来分析一下各个枪手的策略：

如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。

同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率：

第一轮：甲射乙，乙射甲，丙射甲。

甲的活率为24%（40% X 60%）
乙的活率为20%(100% - 80%)
丙的活率为100%（无人射丙）

由于丙100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：

情况1：甲活乙死（24% X 80% = 19.2%）甲射丙，丙射甲：甲的活率为60%，丙的活率为20%。

情况2：乙活甲死（20% X 76% = 15.2%）乙射丙，丙射乙：乙的活率为60%，丙的活率为40%。

情况3：甲乙同活（24% X 20% = 4.8%）重复第一轮。

情况4：甲乙同死（76% X 80% = 60.8%）枪战结束。

据此来计算三人活率：

甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率。

4.6 100个奴隶猜帽子颜色

问题：一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。是否说对，其他奴隶不知道。在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死

2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一

3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑” 99人能100%存活，1人50%能活

另外，此题还有变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？参考回答：增加限制条件后，上面的方法就失效了，此时只能约定偶数位奴隶说他前一个人的帽子颜色，奇数奴隶获取信息100%存活，偶数奴隶50几率存活。

5. 水桶问题

5.1 水资源无限，3L和5L水桶各一个，怎样取4L的水？

初始时0，5
然后3，2
然后0，2
然后2，0
然后2，5
然后1，4

5.2 水资源无限，5L和6L水桶各一个，怎样取3L的水？

step 1 , 6L水桶装满水倒入5L水桶，余下1L水
step 2 , 5L水桶倒空，将6L水桶中剩余的1L水倒入5L水桶
step 3 , 6L水桶再次装满水倒入5L水桶，余下2L水
step 4 , 5L水桶倒空，将6L水桶中剩余2L水倒入5L水桶
step 5 , 6L水桶再次装满水倒入5L水桶，余下3L水

5.3 一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？

初始时为10，0，0；
第二步7，0，3；
然后7，3，0；
然后4，3，3；
然后4，6，0；
然后1，6，3；
然后1，7，2；
然后8，0，2；
然后8，2，0；
然后5，2，3；
然后5，5，0；

5.4 舀酒问题：只有两个舀酒的勺子，分别能舀7两和11两酒，如何舀出2两酒？

问题：据说有人给酒肆的老板娘出了一个难题：此人明明知道店里只有两个舀酒的勺子，分别能舀7两和11两酒，却硬要老板娘卖给他2两酒。聪明的老板娘毫不含糊，用这两个勺子在酒缸里舀酒，并倒来倒去，居然量出了2两酒，聪明的你能做到吗？

思路：大勺子装满酒,再倒满小勺,于是大勺子还有4两,倒出小勺的酒,把大勺的4两倒入小勺中,再次在大勺中装满酒,大小勺加起来就是15两,把大勺中的酒倒入小勺中,使小勺装满,于是大勺中还有8两,倒掉小勺中的酒,再次把大勺中的酒倒入小勺中,使小勺装满,于是大勺中还有1两.重复以上动作一次,就可以得到2两酒

初始0，11
然后7，4
然后0，4
然后4，0
然后4，11
然后7，8
然后0，8
然后7，1
然后0，1
然后1，11
然后7，5
然后0，5
然后5，0
然后5，11
然后7，9
然后0，9
然后7，2

6. 计时问题

6.1 有一个能计时6分钟的小沙漏和一个能计时8分钟的大沙漏，如何计时10分钟？

两个沙漏同时倒置开始计时，等小沙漏漏完，大沙漏还剩2分钟，这时倒置小沙漏继续计时；
大沙漏漏完小沙漏还剩4分钟，再把大沙漏倒置继续计时；
小沙漏漏完大沙漏还剩4分钟，这时准备工作已经完毕；
等待大沙漏漏完（4分钟）+ 小沙漏（6分钟） = 10分钟。

6.2 烧一根绳子需要一个小时，现有若干条相同的绳子，问如何计时15分钟？

点燃绳子A的一头，同时点燃绳子B的两头；绳子B烧完的时候绳子A还剩一半，此时点燃绳子A的另一头开始计时；
15分钟绳子A烧完。

6.3 蜡烛燃烧问题：两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？

点燃第一根的一端，第二根的两端。
第二根烧完代表半小时后，点燃第一根另一端，烧完代表15分钟。

7. 赛马问题

7.1 25匹马5条跑道找最快的3匹马，需要跑几次？

参考回答：7

将25匹马分成ABCDE5组，假设每组的排名就是A1>A2>A3>A4>A5,用边相连，这里比赛5次
第6次，每组的第一名进行比赛，可以找出最快的马，这里假设A1>B1>C1>D1>E1 D1，E1肯定进不了前3，直接排除掉
第7次，B1 C1 A2 B2 A3比赛，可以找出第二，第三名

所以最少比赛需要7次；

7.2 64匹马8条跑道找最快的4匹马，需要跑几次？

参考回答：11

第一步：全部马分为8组，每组8匹，每组各跑一次，然后淘汰掉每组的后四名（需要比赛8场）

第二步：取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛1场）

这个时候总冠军已经诞生，它就是A1，蓝域（它不需要比赛了）。

而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2,A3,A4,B1,B2,B3,C1,C2,D1，共9匹马）

第三步：只要从上面的9匹马中找出跑得最快的三匹马就可以了，但是现在只要8个跑道，怎么办？

那就随机选出8匹马进行一次比赛吧（需要比赛一场）

第四步：上面比赛完，选出了前三名，但是9匹马中还有一匹马没跑呢，它可能是一个潜力股啊，那就和前三名比一比吧，这四匹马比一场，选出前三名。最后加上总冠军，跑得最快的四匹马诞生了！！！（需要一场比赛）

最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场

7.3 25匹马5条跑道找最快的5匹马，需要跑几次？

参考回答：最少8次最多9次

(1) 首先将25匹马分成5组，并分别进行5场比赛之后得到的名次排列如下：

A组： [A1 A2 A3 A4 A5]

B组： [B1 B2 B3 B4 B5]

C组： [C1 C2 C3 C4 C5]

D组： [D1 D2 D3 D4 D5]

E组： [E1 E2 E3 E4 E5]

其中，每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场，选出第1名的马，不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场，此时选择出来的必定是第2名的马，不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场，选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推，第9，10场可以分别决出第4，5名的吗。

因此，依照这种竞标赛排序思想，需要10场比赛是一定可以取出前5名的。

仔细想一下，如果需要减少比赛场次，就一定需要在某一次比赛中同时决出2个名次，而且每一场比赛之后，有一些不可能进入前5名的马可以提前出局。

当然要做到这一点，就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题，希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论：有一些马在前6场比赛之后就决定出局的命运了(下面粉色字体标志出局)。

A组： [A1 A2 A3 A4 A5]

B组： [B1 B2 B3 B4 B5 ]

C组： [C1 C2 C3 C4 C5 ]

D组： [D1 D2 D3 D4 D5 ]

E组： [E1 E2 E3 E4 E5 ]

(3) 第7场比赛是关键，能否同时决出第2，3名的马呢？我们首先做下分析：

在上面的方法中，第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1)，试问？有B1在的比赛，C1、D1、E1还有可能争夺第2名吗？当然不可能，也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名，剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗？

能够优化的关键出来了，我们是否能够通过剩下的3个跑道来决出第3名呢？当然可以，我们来进一步分析第3名的情况？

● 如果A2>B1(即第2名为A2)，那么根据第6场比赛中的(B1>C1>D1>E1)。可以断定第3名只能在A3和B1中产生。

● 如果B1>A2(即第2名为B1)，那么可以断定的第3名只能在A2, B2,C1 中产生。

好了，结论也出来了，只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马，那么这场比赛的第2，3名一定是整个25匹马中的第2，3名。

我们在这里列举出第7场的2，3名次的所有可能情况：

① 第2名=A2，第3名=A3

② 第2名=A2，第3名=B1

③ 第2名=B1，第3名=A2

④ 第2名=B1，第3名=B2

⑤ 第2名=B1，第3名=C1

(4) 第8场比赛很复杂，我们要根据第7场的所有可能的比赛情况进行分析。

① 第2名=A2，第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

● 如果第4名=A4，那么第5名只能在A5、B1中产生。

● 如果第4名=B1，那么第5名只能在A4、B2、C1中产生。

不管结果如何，此种情况下，第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]

② 第2名=A2，第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

● 如果第4名=A3，那么第5名只能在A4、B2、C1中产生。

● 如果第4名=B2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=C1，那么第5名只能在A3、B2、C2、D1中产生。

那么，第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

③ 第2名=B1，第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

情况和②一样，必须角逐第9场

④ 第2名=B1，第3名=B2。那么此种情况下第4名只能在A2、B3、C1中产生。

● 如果第4名=A2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=B3，那么第5名只能在A2、B4、C1中产生。

● 如果第4名=C1，那么第5名只能在A2、B3、C2、D1中产生。

那么，第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

⑤ 第2名=B1，第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

● 如果第4名=A2，那么第5名只能在A3、B2、C2、D1中产生。

● 如果第4名=B2，那么第5名只能在A2、B3、C2、D1中产生。

● 如果第4名=C2，那么第5名只能在A2、B2、C3、D1中产生。

● 如果第4名=D1，那么第5名只能在A2、B2、C2、D2、E2中产生。

那么，第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中产生，因此也必须比赛两场，也就是到第9长决出胜负。

总结：最好情况可以在第8场角逐出前5名，最差也可以在第9场搞定。

8. 过河/过桥问题

8.1 三人三鬼过桥

问题：有三个人跟三个鬼要过河,河上没桥只有条小船,然后船一次只能渡一个人和一个鬼,或者两个鬼或者两个人,无论在哪边岸上,只有是人比鬼少的情况下(如两鬼一人,三鬼两人,三鬼一人)人会被鬼吃,然而船又一定需要人或鬼操作才能航行(要有人或鬼划船),问,如何安全的把三人三鬼渡过河对岸?

参考回答：

先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼。
再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼。
再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼。
最后两人过去。一鬼回来。对面三人。这边三鬼。
剩下的就三个鬼二个过去一个回来在接另外个就OK了。

8.2 限时过桥问题

问题：在一个夜晚，同时有4人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D需要时间分别为：1，2，5，10分钟。问：在17分钟内这四个人怎么过桥？

总共是17分钟

第一步：A、B过花时间2分钟。
第二步：B回花时间2分钟。
第三步：C、D过花时间10分钟。
第四步：A回花时间1分钟。
第五步：A、B再过花时间2分钟。

9. 最优解问题

9.1 猴子搬香蕉

问题：一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。

（提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。）

答案：这种试题通常有一个迷惑点，让人看不懂题目的意图。此题迷惑点在于：走一米吃一根香蕉，一共走50米，那不是把50根香蕉吃完了吗？如果要回去搬另外50根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走50米岂不是需要150根香蕉？

其实不然，本题关键点在于：猴子搬箱子的过程其实分为两个阶段，第一阶段：来回搬，当香蕉数目大于50根时，猴子每搬一米需要吃掉三根香蕉。第二阶段：香蕉数《=50，直接搬回去。每走一米吃掉1根。

我们分析第一阶段：假如把100根香蕉分为两箱。一箱50根。

第一步，把A箱搬一米，吃一根。
第二步，往回走一米，吃一根。
第三步，把B箱搬一米，吃一根。

这样，把所有香蕉搬走一米需要吃掉三根香蕉。

这样走到第几米的时候，香蕉数刚好小于50呢？ 100-(n*3)<50 && 100-(n-1*3)>50

走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦。直接背着走就行。

第二阶段：走一米吃一根。

把剩下的50-17=33米走完。还剩49-33=16根香蕉。

9.2 高楼扔鸡蛋

问题：有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

首先要说明的是这道题你要是一上来就说出正确答案，那说明你的智商不是超过160就是你做过这题。所以建议你循序渐进的回答，一上来就说最优解可能结果不会让你和面试官满意。

1.暴力法

举个栗子，最笨的测试方法，是什么样的呢？把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔.......如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层。

在最坏情况下，这个方法需要扔100次。

2. 二分法

采用类似于二分查找的方法，把鸡蛋从一半楼层（50层）往下扔。

如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层。

如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔......

这个方法在最坏情况下，需要尝试50次。

3.均匀法

如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数，尽可能均衡呢？

很简单，做一个平方根运算，100的平方根是10。

因此，我们尝试每10层扔一次：第1次从10层扔，第2次从20层扔，第3次从30层...一直扔到100层。

这样的最好情况是在第10层碎掉，尝试次数为 1 + 9 = 10次。

最坏的情况是在第100层碎掉，尝试次数为 10 + 9 = 19次。

不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔......一直到95层。

这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次。

4.最优解法

最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔X次，那第一次在第几层扔最好呢？

答案是：从X层扔

假设最优的尝试次数的x次，为什么第一次扔就要选择第x层呢？

这里的解释会有些烧脑，请小伙伴们坐稳扶好：

假设第一次扔在第x+1层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x层。

这样一来，我们总共尝试了x+1次，和假设尝试x次相悖。由此可见，第一次扔的楼层必须小于x+1层。

假设第一次扔在第x-1层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。

这样一来，我们总共尝试了x-2+1 = x-1次，虽然没有超出假设次数，但似乎有些过于保守。

假设第一次扔在第x层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-1层。

这样一来，我们总共尝试了x-1+1 = x次，刚刚好没有超出假设次数。

因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层。

那么算最坏情况，第二次你只剩下x-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；

以此类推我们可得：

x + (x-1) + (x-2) + ... + 1 = 100

这个方程式不难理解：

左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。

右边是总的楼层数100。

下面我们来解这个方程：

x + (x-1) + (x-2) + ... + 1 = 100 转化为 (x+1)*x/2 = 100

最终x向上取整，得到 x = 14

因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。

最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100

举个栗子验证下：

假如鸡蛋不会碎的临界点是65层，那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。

leetcode：https://leetcode-cn.com/problems/egg-drop-with-2-eggs-and-n-floors/

9.3 利用空瓶换饮料，最多喝几瓶

问题：1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？

第一种思路:

拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。

第二种思路:

1000瓶饮料，3个空瓶子能换1瓶饮料，最多可以喝几瓶？
第一种思维：可以考虑成dp思路

初始情况，3个瓶子时将发生一次交换，因此视为特殊情况
之后每增加两个瓶子又可以再换一瓶
即dp[i] = dp[i - 2] + (i - (i - 2)) + 1

由dp[i - 2]可求得dp[i]
(i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）
1即为增加了2个空瓶，之后又可以换一瓶饮料

简化为dp[i] = dp[i - 2] + 2 + 1

public int method(int n) {
     // n为0/1/2的特殊情况省略了
     // 定义dp数组
     int[] dp = new int[n + 1];
     // 初始状态
     dp[0] = 0;
     dp[1] = 1;
     dp[2] = 2;
     for (int i = 3; i <= n; i++) {
       dp[i] = dp[i - 2] + 2 + 1;
    }
     return dp[n];
 }

回归正题

特殊情况：从上面的分析中，留下2个瓶子
剩下998个瓶子相当于每消耗2个瓶子即可获得一瓶，即为499瓶
最后剩下的2个瓶子无法再进行兑换，因此总共为1000 + 499 = 1499

第二种思维：利用借瓶子的思想

因为兑换一瓶饮料需要三个空瓶，这瓶饮料如果是找老板借来的，那么喝完后这个空瓶将会还给他，同时需要附赠给他另外两个空瓶，即每消耗手里两个空瓶就获得一瓶饮料
但是值得注意的是，上面只是一种假设，实际情况老板是不会借给你的，因此我们至少需要保留2个空瓶，这样可以在998个瓶子剩下一个瓶子时，对其进行补足为3个空瓶，从而兑换一瓶新饮料
此时使用998个瓶子进行上述的兑换，将获得499瓶饮料
之前留下的两个瓶子正好无法兑换，最终获得饮料为1000 + 499 = 1499瓶

10. 数字问题

10.1 11-22-33-44问题

问题：有8个数，11-22-33-44，将其排列，要求结果满足：两个1之间有一个数，两个2之间有两个数，两个3之间有三个数，两个4之间有四个数。问这个结果是多少？

答案：①4131-2432 ②2342-1314

10.2 给定随机函数，生成别的随机数

问题：给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？

思路：由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。记住下面这个式子：

RandNN= N( RandN()-1 ) + RandN() ;// 生成1到N^2之间的随机数
可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，
RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙

比如Rand25= 5( Rand5()-1 ) + Rand5()可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写

int rand7(){
  int x=INT_MAX;
  while(x>21){
    x=5*(rand5()-1)+rand5();
  }
  return x%7+1;
}

11. 重量问题

11.1 乒乓球重量问题：8个乒乓球，其中一个重，有一个秤，问至少几次能够找出重的那个乒乓球

2次，分成3堆，3，3，2。

①称3和3，如果一样重，代表重的在2。
②称2个那一堆的。

或

①称3和3，不一样重，重的在3里面重的那堆。
②3个里面随便取2个，一样重，第三个重，不一样重，重的那个就是。

11.2 盐重量问题：有7克、2克砝码各一个，天平一只，如何只用这些物品五次内将140克的盐分成50、90克各一份？

第一次：先分成70和70
第二次：通过7和2砝码将70分成9和61
第三次：通过9克盐和2砝码将61分成50和11

11.3 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？

需要称2次；

天平一边放三个砝码，哪边轻就在哪边，一样重就在剩下的三个砝码中；

现在已经锁定了三个砝码，天平一边放一个，哪边轻是哪个，一样重就是剩下的那个；

11.4 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？

称一次即可；

将砝码分组编号1~10，第1组拿1个砝码、第2组拿2个…第10组拿10个，全部放到秤上计算总克数X； Y = (1*10 + 2 * 10 + … + 10 * 10) - X = 550 - X，Y即为轻的那组的编号。

11.5 药丸问题：有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次；

从药瓶#1取出一粒药丸，从药瓶#2取出两粒，从药瓶#3取出三粒，依此类推。

如果每粒药丸均重1克，则称得总重量为210克（1 + 2 + … + 20 = 20 * 21 / 2 = 210），“多出来的”重量必定来自每粒多0.1克的药丸。

药瓶的编号可由算式(weight - 210) / 0.1 得出。因此，若这堆药丸称得重量为211.3克，则药瓶#13装有较重的药丸。

11.6 药丸问题：你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了？

从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。

依次类推，称其总量。减去10，多的数字就是药丸罐子序号。

12. 灯泡开关问题

12.1 在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？

打开一个开关，过10分钟后关掉开关，并打开另一个开关。进屋确认可知：

亮的灯是由第二次打开的开关控制；
摸上去发热的不发亮的灯是由第一次打开的开关控制
剩下的第三盏灯是由未操作过的开关控制。

12.2一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮。

将灯泡编号 1 ~ 100

步骤一：将灯泡变为全亮或只剩一个为暗

从 1 循环到 98 ，遇到暗的则按它下一个，使之变亮。循环完毕，1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态。

若为亮亮，皆大欢喜，满足题目要求
暗亮、亮暗，达到只剩一个为暗的状态；
若为暗暗。则按下编号 100 的灯泡，使编号 99 、100 变为亮，编号 1 的灯泡变为暗，从而达到只剩一个为暗的状态。

步骤二：将灯泡变为全暗

由于灯泡环形摆放，我们指定暗的灯泡编号为 1 ，将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后，使得所有灯泡变为暗。

步骤三：将灯泡变为全亮

将所有灯泡按一下，灯泡变为全亮;

扩展:

对于 N 个灯泡的任意初始状态 ( N > 3 ) ，能否经过若干次操作使得所有灯泡全亮？

答案：N 个灯泡做分类讨论。

N = 3*k+1一定可以。方法与上述步骤相同，在步骤二中可以将3k个亮的灯泡分为k组。
N = 3*k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗，其余 3 * k 个灯泡分组按即可。因为，对于任意只剩一个为暗的状态，按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态！
N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解；否则，无解。（该结论有待证明）

附:

对于这道题，以下两个状态可以相互转化

大家可以琢磨下，对理解这道题会有帮助。

全暗 <=> 全亮。全暗和全亮状态可以相互转化，方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态，使得全暗变为全亮，全亮也可变为全暗。
剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时，按下该灯泡左右任意一个，就变成了剩两个相邻为暗的状态；剩两个相邻为暗时，按下第二个暗，便可变成了剩一个为暗的状态。

13. 蓝眼/疯狗/耳光问题

13.1 蓝眼睛问题

问题：有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？

有多少个蓝眼睛的人就会花多少天。

假设岛上所有人都是聪明的，蓝眼睛的人四处观察之后，发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的，于是就能推导出自己一定是蓝眼睛的。因此，他会搭乘当晚的飞机离开。

两个蓝眼睛的人看到对方，并不确定c是1还是2，但是由上一种情况，他们知道，如果c = 1，那个蓝眼睛的人第一晚就会离岛。因此，发现另一个蓝眼睛的人仍在岛上，他一定能推断出c = 2，也就意味着他自己也是蓝眼睛的。于是，两个蓝眼睛的人都会在第二晚离岛。

逐步提高c时，我们可以看出上述逻辑仍旧适用。如果c = 3，那么，这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的，那么这两人会在第二晚离岛。因此，如果过了第二晚另外两人还在岛上，每个蓝眼睛的人都能推断出c = 3，因此这三人都有蓝眼睛。他们会在第三晚离岛。

不论c为什么值，都可以套用这个模式。所以，如果有c人是蓝眼睛的，则所有蓝眼睛的人要用c晚才能离岛，且都在同一晚离开。

13.2 疯狗问题

问题：有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪响，第二天没有枪响，第三天开始一阵枪响，问：一共死了几条狗？

死了3条（第几天枪响就有几条）。

从有一条不正常的狗开始，显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。有两条的话思路继续，只考虑有两条不正常狗的人，其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话，同样只考虑那三个人，其中每一个人需要两天的时间证明自己的狗是正常的狗。

13.3 耳光问题

问题：一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？

答案：有三个人戴黑帽。

假设有N个人戴黑帽，当N＝1时，戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N＞1。对于每个戴黑帽的人来说，他能看见N-1顶黑帽，并由此假定自己为白。但等待N-1次还没有人打自己以后，每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。