This is the first day of my participation in Gwen Challenge

Recently prepared to brush a period of time, in this record of some classic questions, updated every day

First day:

Serial number: 45

Difficulty: Medium

Title: Jumping Game II

Link: leetcode-cn.com/problems/ju…

Rule: Given an array of non-negative integers, you start at the first position in the array. Each element in the array represents the maximum length you can jump at that location. Your goal is to get to the last position in the array with the fewest hops.

Example 1:

Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to the last position is 2. Jump from subscript 0 to subscript 1, one step, then three steps to the last position in the array.Copy the code

Example 2:

Input: [2,3,0,1,4] Output: 2Copy the code

Tip:

1 <= nums.length <= 1000
0 <= nums[i] <= 105
Copy the code

Answer:

The first glance is important: greedy algorithms

Because the maximum number of next hops in each step must include other numbers, because it jumps the farthest, which covers all outcomes

code

class Solution: def jump(self, nums: List[int]) -> int: """ Greedy algorithm """ """ n length num Step size left, N = len(nums) num = 0 left, right, cur = 0, 0 # 1. If len(nums) == 1: return 0 # 2. Loop while left < n: # 1. Update the left of the current element each time, right left = right + 1 right = cur + nums[cur] # 4. If right >= n-1: return num + 1 # 2. For I in range(left, right+1): if I + nums[I] > temp: temp = I + nums[I] cur = I # 3. Number of steps + num += 1Copy the code