日常编码问题 24 欢迎回来解决另一个问题！今天，我们正在处理从屋顶掉落的鸡蛋这个非常好的问题，这将涉及两种可能的解决方案：一种非常简单，另一种更聪明。最后一个也让我们有机会谈论一个非常著名的算法。 一如既往，今天的问题是由精彩的时事通讯提供的 ，您也可以免费订阅以获得每日编码挑战。检查一下，并尝试解决您的问题！ 日常编码问题 那就说够了；让我们看看问题所在！ 问题 这个问题是高盛在面试时问到的。让我们看看问题所在。 相同的鸡蛋并可以进入 层的建筑物。你的任务是找到最低的楼层，如果鸡蛋从该楼层掉落，将会导致鸡蛋破裂。鸡蛋一旦破裂，就无法再掉落。如果鸡蛋从 层掉落时破裂，您可以假设从任何大于 的楼层掉落时它也会破裂。 您将获得 N k xth x 编写一个算法，找出在最坏的情况下识别该楼层所需的最少尝试次数。 且  ，我们需要尝试在每一层楼扔鸡蛋，从第一层开始，直到到达第五层，所以我们的解决方案将是  。 例如，如果 N = 1 k = 5 5 因此，我们得到了一些鸡蛋，可以从建筑物的不同楼层扔出。令人遗憾的是，从某个楼层（我们将其称为  ）开始，扔出的鸡蛋落地时不会破裂。 targetFloor 从这一层到下面的每一层，鸡蛋从窗户扔出去都不会破裂。我们需要做的是找到一种有效的方法来找到  。 targetFloor 正如预期的那样，我们将看到两种解决此问题的方法：一种非常简单的方法，它将强力解决该问题，但效率不高。第二种会更有效率，并且会尝试通过打破最少的步骤来解决问题。 它还让我们有机会讨论一个非常著名且重要的算法；这是你需要知道的事情之一……基本上是任何事情！ 设置环境 首先，我们需要设置一些环境，即建筑物和  。为了创建建筑物，我们只需创建一个包含楼层数的数组，从底层到 nᵗʰ 层。然后，我们生成一个随机数，这将是我们的  。 targetFloor targetFloor 我们将再次用 Go 编写这个问题：简单到足以可读，但复杂到足以理解内部机制。   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go 我们首先创建将作为我们的建筑物的数组：我们可以给它我们想要的大小，大小越大，建筑物就会越高。之后，我们使用 Go 中内置的 模块创建 的实例。 math/rand targetFlor 基本上，我们使用当前时间作为源，创建一个介于 0 和建筑物高度（...数组的长度：D）之间的新随机整数。 暴力解决方案 当然，最简单的解决办法就是把每层楼的鸡蛋都扔出去，看看哪一层楼的鸡蛋开始破裂。由于我们有一个包含该信息的变量，因此可以简单地执行 for 循环来解决问题：   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go 虽然这是最简单的解决方案，但不幸的是效率极低。想象一下，如果正确的楼层是顶层：必须打破 100,000 个鸡蛋才能解决问题：这将是一个巨大的煎蛋卷，但相当浪费！ 一般来说，该解决方案的时间复杂度为 O(n)，因为解决方案的复杂度与输入问题的复杂度呈线性增长。但这不是我们能想到的最有效的解决方案。 高效的解决方案 那么我们来考虑一个有效的解决方案。我们可以进行猜测，然后根据猜测的结果调整下一个猜测，而不是一层一层地打破每层楼的每个鸡蛋。 下面是一个例子：假设我们有一栋 10 层楼的建筑，  是 7 楼（当然我们不知道）。我们可以做出以下猜测：  targetFloor 基本上，我们猜测 是建筑物的中间楼层。我们从那里扔鸡蛋，可能的结果有两种： targetFloor 鸡蛋破了，说明我们太高了。我们可以放弃比这层更高的楼层（包括在内），并继续我们的猜测。 鸡蛋没有破裂，意味着我们位置太低或位于正确的楼层。我们丢弃低于这一层的每一层，包括，并且 鉴于此，我们现在对中间楼层或“剩余”建筑物进行另一个有根据的猜测，并应用上面看到的相同策略。我们可以继续这种方法，直到只剩下一层。 如果您碰巧认识到这种方法，那么您是完全正确的：这只是应用于“现实世界”问题的 。二分搜索是一种简单而简洁的 算法，这意味着在每一步中，问题的大小都会减半，直到找到解决方案。 二分搜索 分而治之 这意味着该算法与之前的算法相比要快得多。让我们看看代码！   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go 让我们更深入地了解一下。二分查找函数接受 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) 这意味着该算法的时间复杂度为  。为了对线性解决方案和最后一个解决方案进行一些比较，如果建筑物有 100 层，则线性算法在最坏的情况下需要 100 次迭代，而二分搜索算法需要 log2100 = 6.64，因此需要 7 次迭代。 O(log(n)) 此外，最后一种搜索方式比线性搜索方式越来越高效，因为建筑物增长得越多，二分搜索的效率就越高。对于一栋 1.000.000.000 层的建筑，线性建筑需要 1.000.000.000 步，而二进制建筑则需要 log21.000.000.000 = 29.9，即 30 步。一个巨大的进步！ 结论 就是这个！我希望您喜欢这篇文章，就像我在尝试解决挑战时获得的乐趣一样！如果是的话，请拍一两下，这将是一个很大的支持！如果您喜欢这些类型的文章并想查看更多内容，请关注该页面，因为我会随时发布此类内容。 最后，如果您发现本文有趣或有帮助，并且愿意通过提供咖啡来做出贡献，请随时在我的网站上这样做 页！ 科菲 一如既往，感谢您的阅读！ 尼古拉 也发布 在这里

Read My Stories

該音頻是用故事的原始語言製作的！

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

About Author

註釋

標籤

这篇文章刊登在

Related Stories

创建以用户为中心的加密产品：客户反馈的重要性

成功云迁移的完整指南：策略和最佳实践

看不见的层面：为什么用户访谈是不可替代的资产

数字游民请注意：您需要了解泰国新推出的 DTV 签证

创建以用户为中心的加密产品：客户反馈的重要性

成功云迁移的完整指南：策略和最佳实践

看不见的层面：为什么用户访谈是不可替代的资产

数字游民请注意：您需要了解泰国新推出的 DTV 签证

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps