current position:Home>leetcode 1884. Egg Drop With 2 Eggs and N Floors(python)
leetcode 1884. Egg Drop With 2 Eggs and N Floors(python)
2022-01-31 17:19:48 【Wang Daya】
「 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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311719459712.html
The sidebar is recommended
- Python - convert Matplotlib image to numpy Array or PIL Image
- Python and Java crawl personal blog information and export it to excel
- Using class decorators in Python
- Untested Python code is not far from crashing
- Python efficient derivation (8)
- Python requests Library
- leetcode 2047. Number of Valid Words in a Sentence(python)
- leetcode 2027. Minimum Moves to Convert String(python)
- How IOS developers learn Python Programming 5 - data types 2
- leetcode 1971. Find if Path Exists in Graph(python)
guess what you like
-
leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
-
Python interface automation test framework (basic) -- basic syntax
-
Detailed explanation of Python derivation
-
Python reptile lesson 2-9 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
-
A brief note on the method of creating Python virtual environment in Intranet Environment
-
[worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
-
[Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
-
The unknown side of Python functions
-
Python based interface automation test project, complete actual project, with source code sharing
-
A python artifact handles automatic chart color matching
Random recommended
- Python crawls the map of Gaode and the weather conditions of each city
- leetcode 1275. Find Winner on a Tic Tac Toe Game(python)
- leetcode 2016. Maximum Difference Between Increasing Elements(python)
- Run through Python date and time processing (Part 2)
- Application of urllib package in Python
- Django API Version (II)
- Python utility module playsound
- Database addition, deletion, modification and query of Python Sqlalchemy basic operation
- Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
- Learn how to use opencv and python to realize face recognition!
- Using OpenCV and python to identify credit card numbers
- Principle of Python Apriori algorithm (11)
- Python AI steals your voice in 5 seconds
- A glance at Python's file processing (Part 1)
- Python cloud cat
- Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
- Using pandas to implement SQL group_ concat
- How IOS developers learn Python Programming 8 - set type 3
- windows10+apache2. 4 + Django deployment
- Django parser
- leetcode 1560. Most Visited Sector in a Circular Track(python)
- leetcode 1995. Count Special Quadruplets(python)
- How to program based on interfaces using Python
- leetcode 1286. Iterator for Combination(python)
- leetcode 1418. Display Table of Food Orders in a Restaurant (python)
- Python Matplotlib drawing histogram
- Python development foundation summary (VII) database + FTP + character coding + source code security
- Python modular package management and import mechanism
- Django serialization (II)
- Python dataloader error "dataloader worker (PID XXX) is killed by signal" solution
- apache2. 4 + Django + windows 10 Automated Deployment
- leetcode 1222. Queens That Can Attack the King(python)
- leetcode 1387. Sort Integers by The Power Value (python)
- Tiger sniffing 24-hour praise device, a case with a crawler skill, python crawler lesson 7-9
- Python object oriented programming 01: introduction classes and objects
- Baidu Post: high definition Python
- Python Matplotlib drawing contour map
- Python crawler actual combat, requests module, python realizes IMDB movie top data visualization
- Python classic: explain programming and development from simple to deep and step by step
- Python implements URL availability monitoring and instant push