google经典算法面试题-鸡蛋问题

栏目: 编程工具 · 发布时间: 6年前

内容简介:最近在 leetcode 上看到了一道题Super Egg Drop, 刚好之前看到过一到很类似的题,就是 google 的一道经典的面试题。这里记录一下自己整个的解题思路。给你两个鸡蛋,它们有可能都在某一层楼往下摔就会摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋摔碎的临界点。每次实验即使没摔碎也不会对鸡蛋有损耗。这是一道很经典的需要用到动态规划的题目,我们每一次扔鸡蛋的结果都会影响我们后续扔的次数,比方说我们上来就从 90 层扔,如果碎了,我们就得从

最近在 leetcode 上看到了一道题Super Egg Drop, 刚好之前看到过一到很类似的题,就是 google 的一道经典的面试题。这里记录一下自己整个的解题思路。

google 原题

给你两个鸡蛋,它们有可能都在某一层楼往下摔就会摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋摔碎的临界点。每次实验即使没摔碎也不会对鸡蛋有损耗。

思路

这是一道很经典的需要用到动态规划的题目,我们每一次扔鸡蛋的结果都会影响我们后续扔的次数,比方说我们上来就从 90 层扔,如果碎了,我们就得从1楼一层一层往上扔到90层才能试出结果,如果没碎,我们只需要在 90 ~ 100 这 10 层做实验即可。

要用动态规划的来解这道题,我们首先要列出问题中的状态 每次我们扔鸡蛋的时候,可能会出现两种状态

  • 摔碎,这时下一个鸡蛋就要从最底层一个一个往上试才能试出结果
  • 没碎,则我们需要根据剩余的楼层数来决策出我们下一次丢鸡蛋的楼层数

我们假设第一次我们从 x 层楼往下扔,如果鸡蛋没碎,下一次我们往上走 k 层楼再扔,根据我们的假设我们可以绘制出一个这样的决策树。

google经典算法面试题-鸡蛋问题

为了让最坏的情况不太坏,我们必须要保证每一次的决策最后所需要的次数都尽可能的相等。也就是 1 + k = x。所以每次鸡蛋没碎,我们都要再上一次上升楼层数的基础减少1。

如何确认第一次扔的高度

我们假设我们每次扔鸡蛋都没有碎,第一次从x层开始扔,我们最后一次就必须在100层楼扔了。可以得到式子 x + x - 1 + x - 2 ... + 1 >= 100,根据等差数列求和,我们可以得到 x * (x + 1)/2 >= 100, 得到 x >= 13.45,因为 x 只能取整数,所以第一次我们从14层楼开始扔,得到最坏情况下,我最多需要扔14次可以确认临界点。

放宽到一般情况,n 层楼 2 个鸡蛋,我们可以得到 x + x - 1 + x - 2 ... + 1 >= n 最后算出 x >=

google经典算法面试题-鸡蛋问题

Super Egg Drop

Super Egg Drop 这道题是 google 这道题的升级版。这里的是给定 K 个鸡蛋,N层楼让你求出最小的次数是多少。

我们还是按照动态规划的思路来列出问题中的状态:

  • K = 0的时候,我们是试不出来的
  • K = 1时,我们只能从1楼一层一层往上试,次数为楼层高度 n
  • K = 2时,情况和上面一样
  • k > 2时,需要我们单独分析了

我们设 dp[k][n] 为 k 个鸡蛋,n 层楼时的最优次数。

  • k = 0 , dp[k][n] = 0
  • k = 1, dp[k][n] = n
  • k = 2, dp[k][n] =
    google经典算法面试题-鸡蛋问题

当 k > 2时

google经典算法面试题-鸡蛋问题

假设我们还剩 m 个鸡蛋,还需要实验 n 层楼,此时 1 <= n <= h, 假设我们已经知道了 1 ~ n 层最优解,假设这时候第一次丢的高度为 y ,丢的时候会出现两种情况, 然后可以列出动态方程

碎了

则此时的最优解为 dp(m - 1, y - 1) + 1

没碎

则此时的最优解为 dp(m, n - y) + 1

由此我们可以得到 dp(m, n) = min(max(dp(m - 1, y - 1), dp(m, n - y)) + 1), 1<=y< n,由此我们可以递推的得到 dp(K,N)

JS 实现源码

这题后面还需要优化,由于复杂度较高,需要一定的基础,暂时没有继续优化下去

推荐一个人的博客,把这题分析的非常透彻,有兴趣的可以看看博客地址


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Hacking

Hacking

Jon Erickson / No Starch Press / 2008-2-4 / USD 49.95

While other books merely show how to run existing exploits, Hacking: The Art of Exploitation broke ground as the first book to explain how hacking and software exploits work and how readers could deve......一起来看看 《Hacking》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具