leetcode 1884. Egg Drop With 2 Eggs and N Floors（python）

「 This is my participation 11 The fourth of the yuegengwen challenge 17 God , Check out the activity details ：2021 One last more challenge 」

describe

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.
 Copy code 

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.
 Copy code 

Note:

1 <= n <= 1000
 Copy code 

analysis

According to the meaning , The title gives two identical eggs , And you can enter a building with n A three story building , The floor is marked from 1 To n . There is one. f layer , among 0 <= f <= n Make any higher than f Layers of eggs break when they fall , And anyone from f Eggs that fall at or below the layer will not break .

In every move , We can pick up a whole egg and take it from any floor x（ among 1 <= x <= n） Drop . If the egg breaks , It can't be used anymore . But if the egg doesn't break , We can reuse it later . Return to OK f The minimum number of moves required for the value of .

We can find rules ：

• If 100 floor , We have an egg now , You can only throw it slowly from the first floor to the next floor , Then we'll throw it at the worst 100 Time ;
• If we have two eggs , Throw... In a way similar to dichotomy , The first case is if 50 The building fell and broke one , Then you can only throw the second egg from the first floor to the upper floor and from the bottom to the upper floor , The second case is 50 The building didn't break , Continue to use the dichotomy to find the floor and throw eggs , In short, in the worst case 1+49 Time ;
• In the worst case, the least number of moves is the answer , That is, we throw eggs the least , If we choose from 10 The building began to throw , If it breaks , Use the second egg from 1 Go upstairs and look for , If it doesn't break , Start with the first egg from 20 The building began to throw , Continue the process , The worst case scenario is that the first egg is thrown into 100 The layer is still intact , And then from the 91 From the first floor, go upstairs and throw , The worst need is 10+9 Time ;
• Let's optimize the strategy , If we choose the best floor n The first floor began to throw eggs , As long as the first egg doesn't break , Just go up n-1 layer , That is to say 2n-1 Throw the eggs again , So if the first egg breaks , We use the second egg to check the front n-1 layer , If it's not broken, keep going up n-2 layer , That is to say 3n-3 Throw eggs on the floor , Keep cycling this process , That's it n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100 , namely n (n+1) / 2 >= 100 , The result is rounded up n by 14 , That is, in the worst case, you need to throw 14 Time . That's the first time in 14 The egg thrown from the building is broken , Then use the second egg from 1 The building began to look up .
• So you just need to calculate through the formula to find the answer .

In fact, the whole reasoning process above is also the of the great God on the Internet , I don't understand very deeply , I only know that the code written by mistake has passed .

answer

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
        
        

        	      
		
 Copy code 

Running results

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.
 Copy code 

Original link ：leetcode.com/problems/eg…

The great God explained in detail ：blog.csdn.net/a130737/art…

Your support is my greatest motivation