This is the 24th day of my participation in the August Text Challenge.More challenges in August

1. Title Description

Jumping games

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: true Example 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.

Second, train of thought analysis

  • We can first determine the maximum range from the starting position0 ~ 2All three nodes are reachable. If we want to get to the end by jumping from the beginning to the end, we have to be at 02 The three nodes continuously spread the reachable interval. Diffusion is based on the jumping range of each node. And we know from the picture that when I is equal to 1 we can jump and the range is 3, so it’s 1All four nodes can be reached by jumping.
  • So when should it end? So when we go beyond the range of the array it means that we can go from the starting point to the end point by jumping
  • Since the following nodes are unknown, we need to try range diffusion on all nodes within our current range. The only condition is that we stop at the end of the line. Otherwise you just can’t get there

  • The boundary of the first diffusion

  • The boundary of second diffusion

AC code

public boolean canJump(int[] nums) {
    int max = 0;
    for (int i = 0; i <= max; i++) {
        max = Math.max(max, i + nums[i]);
        if (max+1 >= nums.length) {
            return true; }}return false;
}
Copy the code

  • A maximum range boundary variable is used to control the reachable judgment. The performance is quite good

Four,

  • This is very similar to dynamic programming, but if you think about it, greedy algorithms are more relevant. Because he only cares about the current reachable range.
  • If it is a dynamic program, the previous state will be used later. In this case, you do not need the previous state, but only need to determine the current and subsequent operations.
  • The algorithm needs to continue to deepen!

“Like”