-
Notifications
You must be signed in to change notification settings - Fork 3
/
jumpGame.java
83 lines (64 loc) · 1.97 KB
/
jumpGame.java
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;
public class jumpGame {
/*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*/
public int jumpDP(ArrayList<Integer> a){
//Minimum jump to reach from start to end, else INT_MAX
int n = a.size();
int J[] = new int[n];
for (int i = 0; i < n; i++)
J[i] = Integer.MAX_VALUE;
J[0] = 0;
for (int i = 1; i < n; i++){
for (int j = 0; j < i; j++){
if (a.get(j) + j >= i)
J[i] = Math.min(J[i], J[j]+ 1);
}
}
return J[n -1] == Integer.MAX_VALUE ? -1 : J[n -1];
}
public int jump(ArrayList<Integer> A){
//Minimum jump to reach from start to end, else -1 GREEDY
if (A == null || (A.size() > 1 && A.get(0) == 0))
return -1;
int n = A.size();
int ladder = A.get(0); //largest ladder you have
int stairs = A.get(0); //stairs remaining in my largest ladder
int jump = 1;
for (int i = 1; i < n; i++){
if (i == n -1)
return jump;
if ( i + A.get(i) > ladder)
ladder = i + A.get(i);
stairs --; //use one stair
if (stairs == 0){
jump ++;
stairs = ladder - i;
}
}
return jump;
}
public int canJump(ArrayList<Integer> a) {
if(a.size() <= 1)
return 1;
int max = a.get(0); //max stands for the largest index that can be reached.
for(int i=0; i<a.size(); i++){
//if not enough to go to next
if(max <= i && a.get(i) == 0)
return 0;
//update max
if(i + a.get(i) > max){
max = i + a.get(i);
}
//max is enough to reach the end
if(max >= a.size()-1)
return 1;
}
return 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(new jumpGame().jump(new ArrayList<Integer>(Arrays.asList(2, 3, 1, 1, 4 ))));
}
}