-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathJumpGame.java
More file actions
75 lines (60 loc) · 1.77 KB
/
JumpGame.java
File metadata and controls
75 lines (60 loc) · 1.77 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
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
package leetcode;
import org.junit.Test;
import junit.framework.TestCase;
/**
* Link: https://leetcode.com/problems/jump-game/
*
* @author shivam.maharshi
*/
public class JumpGame extends TestCase {
@Test
public static void test() {
assertEquals(true, canJump(new int[] { 2, 3, 1, 1, 4 }));
assertEquals(false, canJump(new int[] { 3, 2, 1, 0, 4 }));
assertEquals(true, canJump(new int[] {}));
assertEquals(true, canJump(new int[] { 0 }));
assertEquals(true, canJump(new int[] { 1, 0 }));
assertEquals(true, canJump(new int[] { 3, 0, 0, 2, 0, 1, 0 }));
}
public static boolean canJump(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1)
return true;
boolean[] dp = new boolean[nums.length];
dp[0] = true;
// Must come back otherwise will TLE.
for (int i = 0; i < nums.length; i++) {
for (int j = Math.min(i + nums[i], dp.length - 1); j >= i + 1; j--) {
if (dp[j] == true) {
break;
} else {
dp[j] = true;
}
}
}
for (int i = 0; i < dp.length; i++)
if (!dp[i])
return false;
return true;
}
public static boolean canJumpDp(int[] nums) {
return cj(nums, 0, new Boolean[nums.length]);
}
// This DP will throw Stack Overflow in very big inputs.
// Hence implement bottom up DP.
public static boolean cj(int[] nums, int i, Boolean[] dp) {
if (i >= nums.length - 1)
return true;
if (dp[i] != null)
return dp[i];
boolean r = false;
for (int j = 1; j <= nums[i]; j++) {
r = r || cj(nums, i + j, dp);
if (r) {
dp[i] = true;
return dp[i];
}
}
dp[i] = false;
return dp[i];
}
}