leetcode 1884. Egg Drop With 2 Eggs and N Floors(python)

語言: CN / TW / HK

「這是我參與11月更文挑戰的第17天,活動詳情檢視:2021最後一次更文挑戰

描述

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting
  from floor 1 and going up one at a time to find f within 7 more drops. Total drops is 1 + 7 = 8.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9
  and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more
  drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45,
  55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

Note:

1 <= n <= 1000

解析

根據題意,題目給出了兩個相同的雞蛋,並且可以進入一棟有 n 層樓的建築物,樓層的標記為從 1 到 n 。存在一個 f 層,其中 0 <= f <= n 使得任何高於 f 層的雞蛋落下都會破裂,而任何從 f 層或以下的雞蛋落下都不會破裂。

在每次移動中,我們可以拿起一個完整的雞蛋並將其從任何樓層 x(其中 1 <= x <= n)掉落。 如果雞蛋破了,就不能再使用了。 但是如果雞蛋沒有破裂,我們可以在以後重新使用它。返回確定 f 的值所需的最小移動次數。

我們可以找規律:

  • 如果 100 層樓,我們現在有一個雞蛋,只能從一樓往上一層一層慢慢扔,那我們最壞情況要扔 100 次;
  • 如果我們有兩個雞蛋,使用類似二分法的方式扔,第一種情況如果在 50 樓扔摔破了一個,那麼只能用第二個蛋從一樓往上一層一層開始從下往上扔,第二種情況在 50 樓沒有摔破,繼續用二分法找樓層扔雞蛋,總之那麼最壞情況扔 1+49 次;
  • 最壞情況下移動最少的次數就是答案,也就是我們扔的雞蛋次數最少,如果我們選擇從 10 樓開始扔,如果摔破了,用第二個蛋從 1 樓往上一層一層找,如果沒有摔破,用第一個蛋開始從 20 樓開始扔,繼續這個過程,最壞的情況是第一個雞蛋扔到 100 層仍然完好,然後從第 91 層開始一層一層上樓扔,最差需要 10+9 次;
  • 我們再優化策略,假如我們選擇從最佳的樓層 n 樓開始扔雞蛋,只要第一個雞蛋不破,就往上走 n-1 層,也就是在 2n-1 層重新扔雞蛋,這樣如果第一個雞蛋摔破,我們用第二個雞蛋檢查的前面的 n-1 層,如果沒有碎繼續往上走 n-2 層,也就是在 3n-3 樓扔雞蛋,一直迴圈這個過程,那就是 n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100 ,即 n (n+1) / 2 >= 100 ,結果向上取整 n 為 14 ,也就是最差情況需要扔 14 次。也就是第一次在 14 樓扔的蛋就碎了,然後用第二個蛋從 1 樓開始往上找。
  • 所以只需要通過公式計算即即可找出答案。

其實上面整個推理過程也是我看的網上大神的,自己理解的不是很深刻,只知道寫的程式碼誤打誤撞是通過了。

解答

class Solution(object):
    def twoEggDrop(self, n):
        """
        :type n: int
        :rtype: int
        """
        for x in range(n+1):
            if  x * (x+1) // 2 >= n :
                return x

執行結果

Runtime: 8 ms, faster than 99.26% of Python online submissions for Egg Drop With 2 Eggs and N Floors.
Memory Usage: 13.4 MB, less than 77.78% of Python online submissions for Egg Drop With 2 Eggs and N Floors.

原題連結:https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/

大神詳解:https://blog.csdn.net/a130737/article/details/44751691

您的支援是我最大的動力