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:
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. Description:
Suppose you can always get to the last place in the array.
Source: LeetCode link: leetcode-cn.com/problems/ju… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Idea: Greedy algorithm, each time in the reachable range to find the farthest position can be reached next time.
For example:,3,1,1,4 {2}
First, search between the first and second digits of the array (the array starts at 0), and the farthest position is jump to the first digit (the value is 3). Then, search between the second and fourth digits of the array, and the farthest position is the fourth digit (the value is 4).
public int jump(int[] nums) {
if(nums.length == 0 || nums == null) return0; Int result = 0; Int end = 0; Int nextEnd = 0; // Add one to bit 0, but not jump, so subtract onefor(int i = 0; i < nums.length-1; i++){ nextEnd = nextEnd > (nums[i] + i) ? nextEnd : (nums[i] + i); // The current search interval endsif(end == i){ result++; end = nextEnd; }}return result;
}
Copy the code