当你不得不从屋顶扔鸡蛋时：日常编码问题

日常编码问题 24

欢迎回来解决另一个问题！今天，我们正在处理从屋顶掉落的鸡蛋这个非常好的问题，这将涉及两种可能的解决方案：一种非常简单，另一种更聪明。最后一个也让我们有机会谈论一个非常著名的算法。

一如既往，今天的问题是由精彩的时事通讯提供的日常编码问题，您也可以免费订阅以获得每日编码挑战。检查一下，并尝试解决您的问题！

那就说够了；让我们看看问题所在！

问题

这个问题是高盛在面试时问到的。让我们看看问题所在。

您将获得N相同的鸡蛋并可以进入k层的建筑物。你的任务是找到最低的楼层，如果鸡蛋从该楼层掉落，将会导致鸡蛋破裂。鸡蛋一旦破裂，就无法再掉落。如果鸡蛋从xth层掉落时破裂，您可以假设从任何大于x的楼层掉落时它也会破裂。

编写一个算法，找出在最坏的情况下识别该楼层所需的最少尝试次数。

例如，如果N = 1且k = 5 ，我们需要尝试在每一层楼扔鸡蛋，从第一层开始，直到到达第五层，所以我们的解决方案将是5 。

因此，我们得到了一些鸡蛋，可以从建筑物的不同楼层扔出。令人遗憾的是，从某个楼层（我们将其称为targetFloor ）开始，扔出的鸡蛋落地时不会破裂。

从这一层到下面的每一层，鸡蛋从窗户扔出去都不会破裂。我们需要做的是找到一种有效的方法来找到targetFloor 。

正如预期的那样，我们将看到两种解决此问题的方法：一种非常简单的方法，它将强力解决该问题，但效率不高。第二种会更有效率，并且会尝试通过打破最少的步骤来解决问题。

它还让我们有机会讨论一个非常著名且重要的算法；这是你需要知道的事情之一……基本上是任何事情！

设置环境

首先，我们需要设置一些环境，即建筑物和targetFloor 。为了创建建筑物，我们只需创建一个包含楼层数的数组，从底层到 nᵗʰ 层。然后，我们生成一个随机数，这将是我们的targetFloor 。

我们将再次用 Go 编写这个问题：简单到足以可读，但复杂到足以理解内部机制。

我们首先创建将作为我们的建筑物的数组：我们可以给它我们想要的大小，大小越大，建筑物就会越高。之后，我们使用 Go 中内置的math/rand模块创建targetFlor的实例。

基本上，我们使用当前时间作为源，创建一个介于 0 和建筑物高度（...数组的长度：D）之间的新随机整数。

暴力解决方案

当然，最简单的解决办法就是把每层楼的鸡蛋都扔出去，看看哪一层楼的鸡蛋开始破裂。由于我们有一个包含该信息的变量，因此可以简单地执行 for 循环来解决问题：

虽然这是最简单的解决方案，但不幸的是效率极低。想象一下，如果正确的楼层是顶层：必须打破 100,000 个鸡蛋才能解决问题：这将是一个巨大的煎蛋卷，但相当浪费！

一般来说，该解决方案的时间复杂度为 O(n)，因为解决方案的复杂度与输入问题的复杂度呈线性增长。但这不是我们能想到的最有效的解决方案。

高效的解决方案

那么我们来考虑一个有效的解决方案。我们可以进行猜测，然后根据猜测的结果调整下一个猜测，而不是一层一层地打破每层楼的每个鸡蛋。

下面是一个例子：假设我们有一栋 10 层楼的建筑， targetFloor是 7 楼（当然我们不知道）。我们可以做出以下猜测：

基本上，我们猜测targetFloor是建筑物的中间楼层。我们从那里扔鸡蛋，可能的结果有两种：

• 鸡蛋破了，说明我们太高了。我们可以放弃比这层更高的楼层（包括在内），并继续我们的猜测。

• 鸡蛋没有破裂，意味着我们位置太低或位于正确的楼层。我们丢弃低于这一层的每一层，包括，并且

鉴于此，我们现在对中间楼层或“剩余”建筑物进行另一个有根据的猜测，并应用上面看到的相同策略。我们可以继续这种方法，直到只剩下一层。

如果您碰巧认识到这种方法，那么您是完全正确的：这只是应用于“现实世界”问题的二分搜索。二分搜索是一种简单而简洁的分而治之算法，这意味着在每一步中，问题的大小都会减半，直到找到解决方案。

这意味着该算法与之前的算法相比要快得多。让我们看看代码！

让我们更深入地了解一下。二分查找函数接受 4 个参数：

• overArray ，一个整数数组，这是我们要循环的建筑物；

• bottom ，建筑物的底部索引；

• top ，建筑物的顶层索引；

• breakFloor ，保存targetFloor变量，用于检查我们是否可以在建筑物中找到它。

之后，当bottom低于top时，我们循环遍历建筑物：在二分搜索中，当两个位置参数交错和交换时，意味着没有找到搜索到的元素。

因此，如果算法最终处于这种情况，则循环结束并且我们返回-1 ，这意味着我们正在查找的元素不存在于数组中。如果我们仍在搜索元素，我们将应用上图所示的内容。

我们将middlePoint元素计算为bottom和top之间的底部，并检查middlePoint == breakFloor是否。如果是，我们返回middlePoint作为结果。

如果不是，我们相应地调整bottom或top ：如果middlePoint大于breakFloor ，则意味着我们在建筑物上太高，因此我们通过将top可能楼层设置为middlePoint — 1来降低预测。

如果middlePoint小于breakFloor ，我们通过设置为middlePoint+1来调整bottom 。

现在检查一切，在main函数中，我们像以前一样生成环境，并创建一个名为bsFloor的新变量来保存我们的结果。

为了确认我们的算法给我们带来了正确的结果，我们打印出了之前随机生成的bsFloor和targetFloor 。

时间复杂度

正如我们之前预期的那样，该算法比线性算法快得多。由于我们在每一步将建筑物减半，因此我们可以在 log2(n) 中找到正确的楼层，其中 n 等于len(building) 。

这意味着该算法的时间复杂度为O(log(n)) 。为了对线性解决方案和最后一个解决方案进行一些比较，如果建筑物有 100 层，则线性算法在最坏的情况下需要 100 次迭代，而二分搜索算法需要 log2100 = 6.64，因此需要 7 次迭代。

此外，最后一种搜索方式比线性搜索方式越来越高效，因为建筑物增长得越多，二分搜索的效率就越高。对于一栋 1.000.000.000 层的建筑，线性建筑需要 1.000.000.000 步，而二进制建筑则需要 log21.000.000.000 = 29.9，即 30 步。一个巨大的进步！

结论

就是这个！我希望您喜欢这篇文章，就像我在尝试解决挑战时获得的乐趣一样！如果是的话，请拍一两下，这将是一个很大的支持！如果您喜欢这些类型的文章并想查看更多内容，请关注该页面，因为我会随时发布此类内容。

最后，如果您发现本文有趣或有帮助，并且愿意通过提供咖啡来做出贡献，请随时在我的网站上这样做科菲页！

一如既往，感谢您的阅读！

尼古拉

也发布在这里