Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
p>
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [ 3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
Is the array position that can jump the farthest distance, and then ask whether it can jump from index 0 to the last index
Okay, the backtracking method is on top, and everything is backtracking method
Then I just thought about it, but the code still couldn't be written. Refer to the answer
public class Solution {
public boolean< /span> canJumpFromPosition(int position, int [] nums) {
if (position == nums.length-1) {
return true;
}
int furthestJump = Math.min(position + nums[position], nums .length-1);
for (int nextPosition = position + 1; nextPosition <= fu rthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true ;
}
}
return false;
}
public boolean canJump(int[] nums) {
return canJumpFromPosition(0, nums);
}
}
However, the ruthless system prompts, time limit error
The following is awesome Greedy algorithm of coax
class Solution {
public boolean canJump(int[] nums) {
int lastposition = nums.length-1;
for(int i = nums.length-1; i >= 0; i-- ){
if(nums[i]+i >= lastposition){< br /> lastposition = i;
}
}
return lastposition==0;
}
}
True Nima Ingenious work
public class Solution {
public boolean canJumpFromPosition(int position, int[] nums) {
if (position == nums.length-1) {
return true;
}
int furthestJump = Math.min(position + nums[position] , nums.length-1);
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true;
}
}
return false;
}
< br /> public boolean canJump(int[] nums) {
return canJumpFromPosition(0 , nums);
}
}
class Solution {
public boolean canJump(int[] nums) {
int lastposition = nums.length-1;
for(int i = nums.length-1; i >= 0; i--){
if(nums[i]+i >= lastposition){
lastposition = i;
}
}
return lastposition==0;
}
}