日常编码问题 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 签证

Telegram：加密岛通往大陆的桥梁

架构师指南：构建 AI/ML 数据湖参考架构

Floki 的 Valhalla 成为印度环斯里兰卡赛事联合赞助商

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

Telegram：加密岛通往大陆的桥梁

架构师指南：构建 AI/ML 数据湖参考架构

Floki 的 Valhalla 成为印度环斯里兰卡赛事联合赞助商

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps