leetcode-java/src/JumpGame55.java at master · fluency03/leetcode-java · GitHub

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
84
85
86
87
/**
 * 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.
 */


publicclassJumpGame55 {
publicbooleancanJump(int[] nums) {
intlength = nums.length;
if (length == 0 || length == 1 ) {
returntrue;
 }

boolean[] dp = newboolean[length];
dp[0] = true;

for (inti = 1; i <= length - 1; i++) {
for (intj = i - 1; j >= 0; j--) {
dp[i] = dp[j] && (nums[j] >= i - j);
if (dp[i]) {
break;
 }
 }
 }

returndp[length - 1];
 }


/**
 * https://discuss.leetcode.com/topic/3443/simplest-o-n-solution-with-constant-space
 */
publicbooleancanJump2(int[] nums) {
returncanJumpHelper(nums, nums.length);
 }

booleancanJumpHelper(intA[], intn) {
intlast=n-1,i,j;
for(i=n-2;i>=0;i--){
if(i+A[i]>=last)last=i;
 }
returnlast<=0;
 }


/**
 * https://discuss.leetcode.com/topic/7661/java-solution-easy-to-understand
 */
publicbooleancanJump3(int[] A) {
intmax = 0;
for(inti=0;i<A.length;i++){
if(i>max) {returnfalse;}
max = Math.max(A[i]+i,max);
 }
returntrue;
 }


/**
 * https://discuss.leetcode.com/topic/36578/java-98-percentile-solution/7
 */
publicbooleancanJump4(int[] nums) {
if(nums.length < 2) returntrue;

for(intcurr = nums.length-2; curr>=0;curr--){
if(nums[curr] == 0){
intneededJumps = 1;
while(neededJumps > nums[curr]){
neededJumps++;
curr--;
if(curr < 0) returnfalse;
 }
 }
 }
returntrue;
 }
}