高频智力题

高楼扔鸡蛋问题

有一栋楼共**100**层，一个鸡蛋从第**N**层及以上的楼层落下来会摔破，在第**N**层以下的楼层落下不会摔破。给你**2**个鸡蛋，如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

首先要说明的是这道题你要是一上来就说出正确答案，那说明你的智商不是超过160就是你做过这题。

所以建议你循序渐进的回答，一上来就说最优解可能结果不会让面试官满意。

1. 暴力法

从1到100，一层一层试。在最坏情况下，这个方法需要扔100次。 这个办法太蠢了，完全用不上两个鸡蛋这个条件，不建议回答这个方法。

2. 二分法

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

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

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

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

3. 均匀法

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

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

因此，我们尝试每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从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 。

下面是我个人的理解：这个更像是优化版的均匀法，均匀法让你第二次尝试不超过10，但是第一次的位置无法保证（最多要9次，最好一次），这个由于每多一次尝试，楼层间隔就-1，最终使得第一次与第二次的和完全均匀（最差情况）。

但是核心思路是逆向思考，因为即使理解了需要两次的和均匀也很难得到第一次要在哪层楼扔。

一旦理解了这种方法，多少层楼你都不会怕啦~

找砝码问题

有一个天平，九个砝码，一个轻一些，用天平至少几次能找到轻的？

三分法。

答案：2次。

分三份，两份比较，第三份放一边，如果两份相等质量，则说明轻的在第三份。

不论如何，可以确定轻的砝码在某一份的三个之中，再用一次三分法，即可确定。

找玻璃球问题

有十组玻璃球，每组十个，每个玻璃球重**10**g，但其中有一组玻璃球每个只有**9**g，给你一个能显示克数的秤，问你最少几次能找到轻的那一组砝码？

将十组玻璃珠编号1~10，然后第一组拿一个，第二组拿两个以此类推...第十组拿十个
将这些玻璃珠一起放到秤上称出克数x，

则y = 1*10 + 2*10 + 3*10 + ... + 10 * 10 - x

等价于y = (1 + 2 + 3 + ... + 10) * 10 - x = 550 - x

第y组就是轻的那组。

毒药问题

**1000**瓶水，其中有一瓶可以无限稀释的毒药，小白鼠喝了毒水就会死（不论含量多低）。要快速找出哪一瓶有毒，需要几只小白鼠？

二进制思路。

答：2^10 = 1024 > 1000，因此10只小白鼠即可。

给1000瓶水按照二进制编号，比如3号编为00000 00011，拿10个碗，对应10位，对于3号水来说，最后两位是1，则把水混合进最后两个碗中。
最终把10碗水给对应的小白鼠喝，根据最后小白鼠死亡的情况（死即为1，活即为0），即可确定出有毒的那碗水。

生成随机数问题

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

使用 rand5() 生成 rand7()

// 需要随机得到 1-7
public static int rand7() {
    while (true) {
      int row, col, idx;
      // rand5() 返回 1-5
      row = rand5(); // 5 * 5 = 25, 设想一个 5*5 的矩阵
      col = rand5(); // 然后找到小于25的，7的最大倍数21
      idx = col + (row - 1) * 5;
      if (idx <= 21) // 只考虑 1-21，划分成 7 份
        return 1 + (idx - 1) % 7;
    }
}

先手必胜策略问题：

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

卡关键点，每次只能拿15本，所以当剩下6本的时候，不论对面怎么拿你都能赢；

然后推6的倍数：12、18、...、96，也就是一开始要拿4本；

接下来对面拿1，你就拿5，对面拿2，你就拿4，总之让你拿的和对面拿的加起来是6，最终就能赢。

推广到**n**本书，每次拿**1-k**本，怎么保证最后一次是你拿？

瓶子换饮料问题

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

1000 % 3 = 333...1 喝掉1000瓶,可以换333瓶汽水, 余1个空瓶

333 % 3 = 111...0　喝掉333瓶，可以换111瓶汽水, 余0个空瓶

111 % 3 = 37...0 喝掉111瓶，可以换37瓶汽水, 余0个空瓶

37 % 3 = 12...1 喝掉37瓶，可以换12瓶汽水, 余1个空瓶

12 % 3 = 4...0 喝掉12瓶，可以换4瓶汽水, 余0个空瓶

4 % 3 = 1...1 喝掉4瓶，可以换1瓶汽水, 余1个空瓶

此时剩下1瓶汽水 + 3个空瓶，其中3个空瓶可以再换1瓶

此时剩下2瓶，喝掉2瓶，不能再换了。总共：1000 + 333 + 111 + 37 + 12 + 4 + 2 = 1499瓶

重合问题

在一天的**24**小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？

假设时针的角速度为 ω（ω = 1 / 120 (度/秒)），那么分针的角速度就为 12ω，秒针的角速度为 720ω

假设时针和分针在 t 秒后重合，那么分针在 t 时间内走过的角度减去时针在 t 时间内走过的角度，得到的结果肯定是 360 的整数倍

根据上面的规则，可以算出时针和分针重合的时间 – 集合 A

同理也能算出分针和秒针重合的时间 – 集合 B

那么时针、分针及秒针三者重合的时间就是集合 A、B 的交集

结果：

A.length = 22

B.length = 1416

A ∩ B = ['00:00:00', '12:00:00'] = 2

赛马问题（腾讯高频）

有**25**匹马，每场比赛只能赛**5**匹，找最快的**3**匹马，至少要赛多少场？
有**64**匹马，每场比赛只能赛**8**匹，找最快的**4**匹马，至少要赛多少场？
有**25**匹马，每场比赛只能赛**5**匹，找最快的**5**匹马，至少要赛多少场？

25匹马5条跑道找最快的3匹马，需要跑几次？答案：7次

64匹马8条跑道找最快的4匹马，需要跑几次？答案：最少10次，最多11次

此时A1显然是第一名，接下来需要找出第2、3、4名

如果A3拿了第一名

如果A3不是第一，也就是说B1拿了第一

25匹马5条跑道找最快的5匹马，需要跑几次？答案：最少8次，最多9次

现在已经跑了5 + 1=6次

现在已经跑了5 + 1 + 1 = 7次

烧香确定时间问题

有两根不均匀的香，燃烧完都需要一个小时，问怎么确定**15**分钟的时长？

相对时间的思路。

答：设两根香分别为A、B，先把A一端点燃，然后把B的两端都点燃，这样当B烧完的时候，A就还剩下一半（此时能确定半小时），此时把A的另一端也点燃，那么从此刻到A烧完的时间就是15分钟。

掰巧克力问题

**N\*M**块巧克力，每次掰一块的一行或一列，掰成**1\*1**的巧克力需要多少次？
淘汰问题：**1000**个人参加辩论赛，**1V1**，输了就退出，需要安排多少场比赛？

每次拿起一块巧克力，掰一下（无论横着还是竖着）都会变成两块，因为所有的巧克力共有N*M块，所以要掰N*M-1次，减1是因为最开始的一块是不用算进去的。

每一场辩论赛两个人，淘汰一个人，所以可以看作是每一场辩论赛减少一个人，直到最后剩下1个人，所以是1000 - 1 = 999场。