Take time out in the evening and continue to work on a leetcode problem.
The title
Given an array of non-negative integers, nums, 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. Suppose you can always get to the last place in the array.
Example 1: Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of hops 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.
Example 2: Input: nums = [2,3,0,1,4] Output: 2
Train of thought
First of all, the value of each position is the maximum length that can be jumped, but you can also choose to jump closer, so it is not the most brainless value that can be jumped to each cell. Each grid as a starting point, can jump the distance is a line segment, the segment on the points, can be used as the starting point of the next jump, so we can traverse the line segment, numerical subscript + position in the current position is an alternative next five points, so the current optimal jumps to the location, should be a line segment is Max (subscript +), Then iterate over the next reachable segment until you reach the last point, as shown in the figure below
The first value is 2, so the line segment reachable by the first hop is [1,2]. Starting from 1, the line segment can reach as far as 4. Starting from 2, the line segment can reach as far as 3. The alternative starting point for the next jump is 2, 3 and 4, because 4 is the last point, so it can be directly ended. If not, it is to traverse this line segment, which will not be described later.
Java version code
class Solution { public int jump(int[] nums) { int len = nums.length; int ans = 0; int start = 0; int end = 0; while (end < len - 1) { int farest = 0; for (int i = start; i <= end; i++) { farest = Math.max(farest, i + nums[i]); } ans++; start = end + 1; end = farest; } return ans; }}Copy the code