Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to solve the jump game problem with python". In the daily operation, I believe many people have doubts about how to solve the jump game problem with python. The editor has consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubt about "how to solve the jump game problem with python". Next, please follow the editor to study!

Topic: jumping games

Given an array of non-negative integers, you are initially in the first position of the array.

Each element in the array represents the maximum length you can jump at that location.

Your goal is to reach the last position of the array with the least number of hops.

Example:

Input: [2, 3, 1, 1, 1, 4]

Output: 2

Explanation: the minimum number of hops to the last position is 2.

Jump from subscript 0 to subscript 1, skip 1 step, and then jump 3 steps to the last position of the array.

Description:

Suppose you can always reach the last position in the array.

Solve the problem:

As long as the farthest position to which the current position (cur_index) can jump (max_index) is not the last position, it must be at least one step before jumping to the last position.

We find a position index from cur_index + 1 to max_index, the farthest position that can jump to index + nums [index] is the largest, and the number of steps required adds 1 to the original number of steps. Iterate until you can jump to the last position, so that the number of steps is minimum.

Code:

Class Solution:

Def jump (self, nums: List [int])-> int:

Step = 0

Last_len = 0

Max_len = 0

# as long as you don't get to the last element, you have to cycle around (make sure you can get there)

While max_len < len (nums)-1:

Tmp_max_len = max_len

# last_len to max_len choose the largest I + nums [I]

For i in range (last_len, max_len + 1):

Tmp_max_len = max (tmp_max_len, I + nums [I])

Last_len = max_len + 1

Max_len = tmp_max_len

Step + = 1

Return step

At this point, the study on "how to solve the problem of jumping games with python" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.