This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging
preface
Force 45 jump game II as follows:
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 position.
Your goal is to get to the last position in the array with the least number of jumps.
Suppose you can always get to the end of the array.
Example 1:
Input: NUMs = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to the last position is 2. Jump one step from index 0 to index 1, then three steps to the last position in the array.Copy the code
Example 2:
Input: NUMs = [2,3,0,1,4] Output: 2Copy the code
Tip:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
A, thinking
This is a problem that I initially thought was a greedy algorithm, taking a large value in the reachable range, all the way to the end of the array. Until test cases beat me TNT for the umpteenth time
The next position is: the distance traveled + the maximum distance traveled
Nums = [4, 3, 1, 1, 2, 1, 1]
Do you know what the right jump path is? Answer: 4 -> 2 -> 1
Why not select nums[1] = 3 for the first jump?
- Because if you choose
4 - > 3
For this path, the distance traveled is zero1-0 = 1
, the distance traveled isnums[1] = 3
, and for1 + 3 = 4
- And choose
4 - > 2
This path, the distance traveled is zero4-0 = 4
, the distance traveled isnums[4] = 2
, and for4 + 2 = 6
- Obviously choose
4 - > 2
Can go further!
For example
Here, nums = [4, 3, 1, 1, 2, 1, 1] is used as an example
i=1
, the available range isnums[1] ~ nums[4]
, after the maximum distance screening, the final selectionnums[4] = 2
, the jump path is4 - > 2
- To the next starting position,
i=4
, the optional range isnums[5] ~ nums[6]
, after the maximum distance screening, the final selectionnums[6] = 1
, the jump path is4 -> 2 -> 1
- Returns the number of selections
3
Can be
Second, the implementation
The implementation code
The implementation code is consistent with the idea
/** * Greedy algorithm *@param nums
* @return* /
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
int ret = 0;
int len = nums.length;
// From front to back
out:for (int i=0; i<len;) {
int n = nums[i];
int next = -1; // The next position is: distance traveled + maximize distance traveled
for (int j=i+1; j<n+i+1; j++) {
if (j == len -1) {
ret ++;
break out;
}
if (next == -1) {
next = j;
continue;
}
int currentDistance = (j-i) + nums[j]; // The current distance sum
int nextDistance = (next-i) + nums[next]; // Next distance sum
if (currentDistance > nextDistance) {
next = j;
}
}
ret ++;
i = next;
}
return ret;
}
Copy the code
The test code
public static void main(String[] args) {
int[] nums = {4.1.1.3.1.1.1};
new Number45().jump(nums);
}
Copy the code
The results of
Third, summary
Thank you for seeing the end, it is my great honor to help you ~♥