-
Notifications
You must be signed in to change notification settings - Fork 0
/
jump_game.js
59 lines (51 loc) · 1.32 KB
/
jump_game.js
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
// https://leetcode.com/problems/jump-game/description/
// 55. Jump Game
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let as_far_as_possible = 0;
for (let i = 0; i < nums.length; i++) {
if (as_far_as_possible < i) return false
as_far_as_possible = Math.max(as_far_as_possible, i + nums[i])
}
return true;
};
console.log("Jump Game")
console.log(canJump([2,3,1,1,4]))
// Output: true
console.log(canJump([3,2,1,0,4]))
// Output: false
// ########################
// https://leetcode.com/problems/jump-game-vii/
// 1871. Jump Game VII
/**
* @param {string} s
* @param {number} minJump
* @param {number} maxJump
* @return {boolean}
*/
var canReach = function (s, minJmp, maxJmp) {
let n = s.length;
let canReach = new Array(n).fill(0);
let [from, to] = [0, 1];
canReach[from]++;
if (to < n) canReach[to]--;
let sum = 0;
for (let i = 0; i < n; i++) {
sum += canReach[i];
canReach[i] = sum;
if (canReach[i] === 1 && s[i] === "0") {
let [from, to] = [i + minJmp, i + maxJmp + 1];
if (from < n) canReach[from]++;
if (to < n) canReach[to]--;
}
}
return s[n - 1] === "0" && canReach[n - 1] === 1;
}
console.log("Jump Game VII")
console.log(canReach("011010", 2, 3))
// Output: true
console.log(canReach("01101110", 2, 3))
// Output: false