-
Notifications
You must be signed in to change notification settings - Fork 2.5k
Expand file tree
/
Copy path0055-jump-game.js
More file actions
100 lines (83 loc) · 2.27 KB
/
0055-jump-game.js
File metadata and controls
100 lines (83 loc) · 2.27 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
* Time O(2^N) | Space O(N)
* @param {number[]} nums
* @return {boolean}
*/
var canJump = (nums, index = 0) => {
const isBaseCase = index === nums.length - 1;
if (isBaseCase) return true;
const furthestJump = Math.min(index + nums[index], nums.length - 1);
for (let nextIndex = index + 1; nextIndex <= furthestJump; nextIndex++) {
if (canJump(nums, nextIndex)) return true;
}
return false;
};
/**
* Time O(N^2) | Space O(N)
* @param {number[]} nums
* @return {boolean}
*/
var canJump = (nums) => {
const memo = new Array(nums.length).fill(0);
memo[memo.length - 1] = 1;
return canJumpFromIndex(nums, memo);
};
const canJumpFromIndex = (nums, memo, index = 0) => {
if (memo[index] !== 0) return memo[index] === 1;
const furthestJump = Math.min(index + nums[index], nums.length - 1);
for (let nextIndex = index + 1; nextIndex <= furthestJump; nextIndex++) {
if (!canJumpFromIndex(nums, memo, nextIndex)) continue;
memo[index] = 1;
return true;
}
memo[index] = -1;
return false;
};
/**
* Time O(N^2) | Space O(N)
* @param {number[]} nums
* @return {boolean}
*/
var canJump = (nums) => {
const memo = new Array(nums.length).fill(0);
memo[memo.length - 1] = 1;
for (let i = nums.length - 2; 0 <= i; i--) {
const furthestJump = Math.min(i + nums[i], nums.length - 1);
for (let j = i + 1; j <= furthestJump; j++) {
const isGood = memo[j] === 1;
if (isGood) {
memo[i] = 1;
break;
}
}
}
return memo[0] === 1;
};
/**
* Time O(N) | Space O(1)
* @param {number[]} nums
* @return {boolean}
*/
var canJump = (nums, max = 0, index = 0) => {
while (index < nums.length) {
const num = nums[index];
const jumps = num + index;
const canNotReachEnd = max < index;
if (canNotReachEnd) return false;
max = Math.max(max, jumps);
index++;
}
return true;
};
/**
* Time O(N) | Space O(1)
* @param {number[]} nums
* @return {boolean}
*/
var canJump = (nums, right = nums.length - 1) => {
for (let i = right; 0 <= i; i--) {
const isJumpable = right <= i + nums[i];
if (isJumpable) right = i;
}
return right === 0;
};