[Leetcode] Problem Series of Jump Game
By Long Luo
This article is the solution Leetcode Jump Game Problems Series.
1. 55. Jump Game
Brute Force
1 | public boolean canJump(int[] nums) { |
Analysis
- Time Complexity: \(O(n^2)\)
- Space Complexity: \(O(n)\)
Greedy
Jump to the farest postion.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public boolean canJump(int[] nums) {
int len = nums.length;
int maxIdx = 0;
for (int i = 0; i < len; i++) {
int steps = nums[i];
if (maxIdx >= i) {
maxIdx = Math.max(maxIdx, i + steps);
if (maxIdx >= len - 1) {
return true;
}
}
}
return false;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(1)\)
2. 45. Jump Game II
DP
1 | public static int jump_dp(int[] nums) { |
Analysis
- Time Complexity: \(O(n^2)\)
- Space Complexity: \(O(n)\)
Greedy
1 | public int jump(int[] nums) { |
Think reverse, from destination to origin position.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int jump(int[] nums) {
int ans = 0;
int position = nums.length - 1;
while (position > 0) {
for (int i = 0; i < position; i++) {
if (i + nums[i] >= position) {
ans++;
position = i;
break;
}
}
}
return ans;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(1)\)
3. 1306. Jump Game III
BFS
BFS Solution: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
32public boolean canReach_bfs_opt(int[] arr, int start) {
if (arr[start] == 0) {
return true;
}
int len = arr.length;
boolean[] visited = new boolean[len];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int curPos = queue.poll();
if (arr[curPos] == 0) {
return true;
}
int right = curPos + arr[curPos];
if (right >= 0 && right < len && !visited[right]) {
visited[right] = true;
queue.offer(right);
}
int left = curPos - arr[curPos];
if (left >= 0 && left < len && !visited[left]) {
visited[left] = true;
queue.offer(left);
}
}
return false;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
DFS
1 | public boolean canReach_dfs(int[] arr, int start) { |
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
4. 1345. Jump Game IV
BFS
1 |
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
5. 1340. Jump Game V
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
6. 1696. Jump Game VI
1696. Jump Game VI1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public static boolean canJump(int[] nums) {
int len = nums.length;
int maxIdx = 0;
for (int i = 0; i < len; i++) {
int steps = nums[i];
if (maxIdx >= i) {
maxIdx = Math.max(maxIdx, i + steps);
if (maxIdx >= len - 1) {
return true;
}
}
}
return false;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
7. 1871. Jump Game VII
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote?? if you like?? it. Thank you:-)
Explore More Leetcode Solutions.