今天想跟大家分享一個有意思的面試題，這讓我再一次感嘆思維的奇妙，接下來我們一起看看吧~

首先來看看題目：

你有2顆雞蛋，需要以最少的嘗試次數(shù)來判斷在100層的高樓上，哪一層樓是雞蛋的安全層。

換句話說，就是需要確定我們從哪一層樓扔雞蛋下去，雞蛋恰好不會摔碎。高于安全層雞蛋都會碎，低于安全層都不會碎。比如雞蛋在第1層沒有摔碎，在第2層摔碎了，那么雞蛋的安全層就是第1層。

這里有幾個假設條件：

1. 沒有摔碎的雞蛋可以重復使用；

2. 每顆雞蛋的堅硬程度都是相同的。

這道題乍一看挺簡單的，但其實解答相對復雜，而且解法多種多樣，要在面試時邏輯清楚地表達完整思路，不僅要求面試者的知識儲備要廣、反應能力要快，邏輯思維和語言表達能力也是必不可少的。

成為經(jīng)典可謂當之無愧。

解法1：簡單粗暴

我們先來個最省事兒的方法：假設我們只有一顆雞蛋，顯然只有從一樓開始扔，逐層試探，直到雞蛋摔碎，安全層就是第N-1層。

但是缺點想必大家也看出來了，這是拼運氣啊，最壞情況需要扔100次。

用一顆雞蛋的方法雖然簡單粗暴，但也是給兩顆雞蛋的情況縷清一些思路。

簡單寫一下如何實現(xiàn)：

// 假設arr表示100層樓,每層樓雞蛋會不會碎,如果arr[i] === 1 表示i層樓的雞蛋會碎,arr[i] === 0表示第i層樓的雞蛋不會碎

// 簡單暴力
const throwEggs1 = (arr) => {
  for(let i = 1; i <= 100; i++) {
    if (arr[i] === 1) {
      return i
    }
  }
}

解法2：常規(guī)二分

有兩顆雞蛋，二分法想必是大多數(shù)同學腦海里浮現(xiàn)的第一個念頭吧？

我們先從50樓扔一顆雞蛋，如果沒碎，就往上繼續(xù)二分，到75樓繼續(xù)扔······

這是比較順利的情況，如果不順利呢，比如我們從50樓扔雞蛋，直接碎了，那就只有一顆雞蛋了。

這時候我們就回到解法1了，只能從1樓開始遍歷，又是拼運氣的時候了，要是運氣好，1樓雞蛋就沒了，那測試次數(shù)就是1+1=2次，但最壞情況就是1+49=50次。

這么多次，顯然是不能通過google面試的。

// 常規(guī)二分

const throwEggs2 = (arr) => {
  let left = 1
  let right = 100
  let mid = 0
  while(left <= right) {
    mid = Math.floor(left + right) / 2
    if (arr[mid] === 0) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return mid
}

解法3：均衡切割

雖然二分法不夠優(yōu)秀，但體現(xiàn)了切分范圍的思想。

我們的基本思路是，將100層切分成兩個維度，由兩個雞蛋分別控制一個維度。

一個維度是用第一顆雞蛋分金定穴，另一個維度是用第二顆雞蛋在前蛋的基礎上進行遍歷。

換言之，我們是將100層切分成若干個區(qū)塊，由第一顆雞蛋確定最高安全樓層所屬的區(qū)塊，再由第二顆雞蛋逐層確定其具體的位置。

在1-100層樓之間，假設我們從上往下嘗試，即從100層開始扔第一顆蛋，大概率是碎了，那第二顆蛋便又回到了解法1。

所以，我們應該從下往上進行劃分、嘗試，這樣即使第一顆雞蛋碎了，用第二顆蛋遍歷的成本也比較低。

比如第一顆蛋每10層扔一次，第一次從10層扔，第二次從20層扔，第三次從30層扔……一直扔到100層。

第二顆蛋就只用在第一顆蛋摔碎的層數(shù)和前一次的安全層之間的9層進行范圍遍歷。

也就是說，要是第一顆雞蛋在第30層摔碎了，那就拿第二顆蛋從21層到29層逐層嘗試。

這樣的最好情況就是第一顆蛋在第10層碎掉，總的嘗試次數(shù)為1+1=2次。

最壞的情況是在第100層碎掉，總嘗試次數(shù)為10+9=19次。

// 均衡切割
const throwEggs3 = (arr) => {
  let count = 0
  // 第一個雞蛋
  for (let i = 1; i < 10; i++) {
    if (arr[i * 10] === 1) {
      count = i * 10
      break
    }
  }
  // 第二個雞蛋
  for(let i = count - 1; i >= count - 10; i--) {
    if (arr[i] !== 1) {
      return i
    }
  }
}

解法4：微妙平衡

上面的方法，看似已經(jīng)比較完美了。

但是我們再具像化一點，就能發(fā)現(xiàn)問題：第一顆雞蛋能快速定位安全樓層低的情況，但如果安全樓層位置越高，耗時就會越久，而第二顆雞蛋在每個區(qū)塊內(nèi)的消耗，都是一樣的。

如果雞蛋的最高安全層為18或者98，用解法3的思路的話，這兩種情況的總嘗試次數(shù)并不一樣：

最高安全樓層為18時，第一顆雞蛋試了2次就定位了區(qū)塊；而最高安全樓層為98時，第一顆雞蛋試了10次才定位了區(qū)塊。

雖然第二顆雞蛋在區(qū)塊內(nèi)部的逐層嘗試次數(shù)是一樣的，但98層對應的總嘗試次數(shù)就多太多了。

原因就是區(qū)塊完全均勻劃分對大數(shù)不利。

明白了這個缺陷，也就知道了改進的基本思想：要對100找出一種二維區(qū)塊劃分，但不是均勻劃分。

對于比較小的區(qū)塊部分，其包含的樓層范圍可以適當增加；越向大數(shù)部分走，其包含的樓層范圍越來越小。從下往上，每一個區(qū)塊內(nèi)所含樓層遞減。

在最高安全樓層比較低的情況下，第一顆雞蛋嘗試的次數(shù)少；在最高安全樓層比較高的情況下，則第二顆雞蛋嘗試的次數(shù)少。

就是用第二顆雞蛋嘗試次數(shù)的減少來彌補第一顆雞蛋需要的嘗試次數(shù)的遞增，使兩顆雞蛋在不同維度上的嘗試次數(shù)此消彼長，達到一種總體上的平衡。

每上一個區(qū)塊，第一顆雞蛋消耗的次數(shù)就+1，我們索性就假設每個區(qū)塊包含的樓層數(shù)逐級遞減1，以達到平衡。

那么每個區(qū)塊包含的層數(shù)應該如何劃分呢？

我們假設第一個區(qū)塊有X層，那么第二個就是X-1，以此類推，我們就得到了一個方程式：

X+（X-1）+（X-2）+···+3+2+1≥100

可以看出來，這時候區(qū)塊個數(shù)和第一個區(qū)塊包含的層數(shù)其實是相等的。

現(xiàn)在我們回過頭來，再仔細看看方程式，是不是有點熟悉，不就是等差數(shù)列求和么！

所以我們化簡方程式：

X(X+1)/2≥100

這里X最小值我們向上取整，得到14。

有同學會問為什么一定到1呢，最后一個區(qū)塊一定只有1層嗎？

不是的，到1是表示在X個區(qū)塊的情況下，最多能覆蓋的層數(shù)。

比如我們這個例子，X是14，求出的樓層總數(shù)是105，也就是可以覆蓋105層，題目要求的100層當然綽綽有余。

由此，第一個區(qū)塊包含14層樓，即1到14層；

第二個區(qū)塊包含13層樓，即15到27層；

第三個區(qū)塊包含12層樓，即28到39層；

······

第一顆雞蛋依次試第14、27、39、50、60、69、77、84、90、95、99、100層。只要期間任何一次雞蛋碎了，就拿第二顆雞蛋從上一次的安全層之后開始逐層嘗試，直至第二顆雞蛋也摔碎為止。

用這個方法，總次數(shù)一定不會超過14次。

因為最高安全樓層越高，第一顆雞蛋的嘗試次數(shù)也就越多，但第二顆雞蛋的嘗試次數(shù)隨之越來越少，兩者始終維持著一種微妙的平衡，最后總的嘗試次數(shù)波動也不會太大。

下面是全部的代碼實現(xiàn)：

// 假設arr表示100層樓,每層樓雞蛋會不會碎,如果arr[i] === 1 表示i層樓的雞蛋會碎,arr[i] === 0表示第i層樓的雞蛋不會碎

// 暴力
const throwEggs1 = (arr) => {
  for(let i = 1; i <= 100; i++) {
    if (arr[i] === 1) {
      return i
    }
  }
}

// 常規(guī)二分

const throwEggs2 = (arr) => {
  let left = 1
  let right = 100
  let mid = 0
  while(left <= right) {
    mid = Math.floor(left + right) / 2
    if (arr[mid] === 0) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return mid
}

// 均衡切割
const throwEggs3 = (arr) => {
  let count = 0
  // 第一個雞蛋
  for (let i = 1; i < 10; i++) {
    if (arr[i * 10] === 1) {
      count = i * 10
      break
    }
  }
  // 第二個雞蛋
  for(let i = count - 1; i >= count - 10; i--) {
    if (arr[i] !== 1) {
      return i
    }
  }
}

// 微妙平衡
const throwEggs4 = (arr) => {
  let block = 10
  let count = 0
  // block(block + 1) / 2 >= 100
  while(block * block + block < 100 * 2) {
    block++
  }
  // 第一個雞蛋的嘗試
  let temp = block // 每層區(qū)塊的最后一個
  while(temp <= 100) {
    if (arr[temp] === 1) {
      count = temp
      break
    }
    --block
    temp += block
  }

  // 第二個雞蛋的嘗試
  for(let i = count - 1; i >= count - block; i--) {
    if (arr[i] === 0) {
      return i
    }
  }
}

除了文中我們討論的解法，這道題也還有其他解法可以選擇，如果感興趣大家可以自己研究研究，也歡迎來一起討論！

憑心而論，要是在毫無準備的情況下，一般人只能想到第一種，做過算法題的，應該能夠想到第二種，想到解法三已經(jīng)是最優(yōu)解了，能在這么短的時間內(nèi)想到解法四的大神是鳳毛麟角。

好了，祝大家周末愉快！

最后，希望大家讀完這篇文章都能有所收獲！文章來源地址http://www.zghlxwxcb.cn/news/detail-675441.html

到了這里，關于谷歌面試-扔雞蛋的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！