The title
Given an array of non-negative integers, nums, you start at the first index of the array.
Each element in the array represents the maximum length you can jump at that location.
Determine if you can reach the last index.
Example 1
Input: nums = [2,3,1,1,4] output: trueCopy the codeExample 2
Input: nums = [3,2,1,0,4] Output: false But this subscript has a maximum jump length of 0, so you can never reach the last subscript.Copy the codeTrain of thought
Array class algorithm, certainly not traversal; So let’s go through it
DFS solution
What comes to mind for the element nums[I] in position I?
According to the title, most people’s first reaction would be: what’s next? ;
I + 1, I + 2… i + nums[i]
So the next thing you know, what’s the best place to jump?
At this time, the problem of the previous step is impossible to judge, then how to do?
No way, only each one to try again ~
DFS (depth-first search) algorithm is the same as DFS (depth-first search) algorithm, recursively and backtracking, but this problem has very little backtracking. If only DFS is used, the time complexity of the algorithm will be very high, as can be seen below:
The first editionDFSThe following code
/ * * *@param {number[]} nums
* @return {boolean}* /
var canJump = function (nums) {
// Define the identifier, whether the last position has been reached
let ans = false;
let n = nums.length;
/ * * * *@param {Number} Idx Current jump position *@returns null
*
* @description Pass a jump position from which to jump to all possible next positions */
const jump = (idx) = > {
// If the current position is larger than the array length, it is illegal, no need to continue, the first prune
if (idx >= n) return;
// If the current position is the last position, or has jumped to the last position, do not need to proceed to the second prune
if (idx === n - 1 || ans) {
ans = true;
return;
}
// The current maximum jump distance
let loop = nums[idx];
// If the current maximum distance is larger than the distance between idx -> n, then we can reach the last position, the third pruning
if (loop >= (n - idx)) {
ans = true;
return;
}
// In turn, jump to the next location and continue to call jump recursion
for (let i = 1; i <= loop; i++) { jump(idx + i); }}// Start the recursive function from position 0
jump(0);
return ans;
};
Copy the codeWhen submitting leetCode, the time limit is displayed as 😭😭😭
There is another important prune operation that I forgot. For position I, you only need to call the jump function once. The following operations are repeated.
So you can use an auxiliary array that marks if I called jump,
The second editionMemory DFSThe following code
Three lines of code were added, all vis related, but the time complexity was optimized to approximate O(n), which is space timeCopy the code / * * *@param {number[]} nums
* @return {boolean}* /
var canJump = function (nums) {
// Define the identifier, whether the last position has been reached
let ans = false;
let n = nums.length;
// The auxiliary function is used to determine whether I is evaluated
let vis = new Array(n).fill(false);
/ * * * *@param {Number} Idx Current jump position *@returns null
*
* @description Pass a jump position from which to jump to all possible next positions */
const jump = (idx) = > {
// If the current position is larger than the array length, it is illegal, no need to continue, the first prune
// Add a pruning operation as calculated by vis[I]
if (idx >= n || vis[idx]) return;
vis[idx] = true;
// If the current position is the last position, or has jumped to the last position, do not need to proceed to the second prune
if (idx === n - 1 || ans) {
ans = true;
return;
}
// The current maximum jump distance
let loop = nums[idx];
// If the current maximum distance is larger than the distance between idx -> n, then we can reach the last position, the third pruning
if (loop >= (n - idx)) {
ans = true;
return;
}
// In turn, jump to the next location and continue to call jump recursion
for (let i = 1; i <= loop; i++) { jump(idx + i); }}// Start the recursive function from position 0
jump(0);
return ans;
};
Copy the codeDynamic programming
In the above solution, the main direction of thinking is what is the next step
So position I, let’s think about it, is I currently reachable? And if so, under what conditions?
It is not difficult to figure out: for I to be reachable, there must be a j before I such that j + nums[j] >= I
Then dynamic programming can be used to solve this problem:
Dynamic programmingThe code for the solution is as follows
/ * * *@param {number[]} nums
* @return {boolean}* /
var canJump = function(nums) {
let n = nums.length;
// create a new dp array. Dp [I] indicates whether I is reachable
let dp = new Array(n).fill(false);
// Initial condition, position 0 must be reached
dp[0] = true;
for(let i = 1; i < n; i++) {
// Iterate over elements less than I
for(let j = 0; j < i; j++) {
// if dp[j] is true, dp[j] is reachable
// if nums[j] + j >= I, dp[j] is available
// Break the loop
if(dp[j] && nums[j] + j >= i) {
dp[i] = true;
break; }}}// The last element of the dp array
return dp[n - 1];
};
Copy the codeFound no, compared with the first algorithm, dynamic programming solution code amount is much less!!
greedy
And the idea of the greedy algorithm is, every time, you pick the choice that looks best at the moment, regardless of the overall impact, so let’s do this again
Is it also possible to determine whether the element at position I can be reached by dynamically changing the current maximum jump -> jumpMax variable?
For example, for position 2, If jumpMax is smaller than 2, position 2 cannot be reached, otherwise it can be reached
So if you can’t get to it, do you still need to judge the elements after position 2?
For [0, 0, 1, 3], I == 1; JumpMax == 0, position 1 is obviously unreachable, and positions after position 1 are unreachable
Greedy algorithmThe following code
/ * * *@param {number[]} nums
* @return {boolean}* /
var canJump = function(nums) {
let n = nums.length;
// The current maximum distance, initially the value of the first nums element
let jumpMax = nums[0];
for(let i = 0; i < n; i++) {
// If the current maximum distance is less than the current index I, position I cannot be reached
if(jumpMax < i) return false;
-> I + nums[I] is the maximum distance that can be traveled at the position of I
jumpMax = Math.max(jumpMax, i + nums[i]);
// If the current maximum distance is greater than the length of the array, then the last position can be reached
if(jumpMax >= n - 1) return true;
}
// Each element can be reached, as well as the last element
return true;
};
Copy the codesummary
The above three solutions, one with less code than the other, and the last one with the lowest O(n) time complexity, are the most efficient, but also the most difficult to think of
Algorithm this thing, you don’t practice, it will ignore you ~
LeetCode 👉 HOT 100 👉 Jump game – medium title ✅
Collection: LeetCode 👉 HOT 100, will update when you are free, we support a lot, click a like 👍
If you have a good solution or find something wrong with this article, please leave a comment at 😄