This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Leetcode55: Jump game

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

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.

Analysis of the problem

Method 1

This scheme adopts greedy algorithm. The main idea of greedy algorithms is to try to get the maximum length that you can jump to. From the perspective of a node, as long as the node can be reached and the value on the node is n, then x+1,x+2 after the node x can be reached… X + n nodes. So the idea is to start at the first node of the array and iterate backwards. At each node, the maximum node that the node can reach is recorded. At the same time, variables are used to save the current maximum node that can be reached. The maximum node calculated for each node is compared with the maximum node recorded in the whole, and the larger value is the maximum node that can be reached by the current array. After traversing the array once, you can get the maximum node that all the elements of the array can reach logically. The node is then compared to the length of the array. If the maximum node is greater than or equal to the length of the array minus 1, we can determine that we can reach the end node of the array. Otherwise, it cannot. There’s actually a place where you can optimize and compare the maximum value in real time as you compute each of the largest nodes in the array. If the target value can be achieved, the loop can be closed ahead of time to reduce the number of iterations and optimize. At this point, the problem is solved.

public boolean canJump(int[] nums) {
    int maxLength = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] + i > maxLength && i <= maxLength){
            maxLength = nums[i] + i;
        }
    }
    return maxLength >= nums.length-1;
}
Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (1)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.