Repository navigation
Expand file tree
/
Copy path_55.java
More file actions
47 lines (39 loc) · 1.52 KB
/
Copy path_55.java
File metadata and controls
47 lines (39 loc) · 1.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.fishercoder.solutions;
/**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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.*/
public class _55 {
public static boolean canJump_greedy(int[] nums) {
int farthest = nums[0];
for(int i = 0; i < nums.length; i++){
if(i <= farthest && nums[i]+i > farthest) {
//i <= farthest is to make sure that this current i is within the current range
// nums[i]+i > farthest is to make sure that it's necessary to update farthest with current nums[i]+i
farthest = nums[i]+i;
}
}
return farthest >= nums.length-1;
}
//this normal dp ends in TLE for extreme test cases
public static boolean canJump_dp(int[] nums) {
boolean[] can = new boolean[nums.length];
can[0] = true;
for(int i = 0; i < nums.length; i++){
int reach = nums[i];
if(can[i]){
for(int j = i+1; j < nums.length && j <= i+reach; j++){
can[j] = true;
}
}
}
return can[nums.length-1];
}
public static void main(String...strings){
// int[] nums = new int[]{1,2};
int[] nums = new int[]{0,2,3};
System.out.println(canJump_greedy(nums));
}
}