This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

preface

The jumping game is as follows:

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 code

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.Copy the code

A, thinking

This question is similar to the forty-fifth question of Libutton – jumping game II. I was also going to use the greedy algorithm (the distance traveled + maximize the distance traveled). If the last index cannot be reached even under the optimal strategy, it means that it cannot be reached.

However, as my smart girlfriend reminded me, this problem only needs to determine whether the end of the array can be reached, and does not need to select the minimum number of jumps, so there is no need to use greedy algorithms (effectively reducing the algorithm complexity, amazing!).

Since the ultimate goal is to reach the end of the array, we can: traverse the end of the array, and update the current index with the new trailing index if one of the subscripts reaches the end. Returns True if the last trailing index is the first index of the array

For example

Take nums = [3, 2, 2, 0, 4] as an example. The initial tail subscript is 4

If nums[I] >= lastJump -i indicates that the current subscript reaches the trailing subscript

  1. i=3When, not satisfiednums[3] >= 4 - 3(0 < 1), so the tail subscript cannot be reached
  2. i=2When to meetnums[2] >= 4 - 2(2 == 2), can reach the tail subscript, update the tail subscript is2

  1. i=1When to meetnums[1] >= 2 - 1(2 > 1), can reach the tail subscript, update the tail subscript is1

  1. i=0When to meetnums[0] >= 1 - 0(3 > 1), can reach the tail subscript, update the tail subscript is0

  1. In this case, the tail subscript coincides with the head subscript, indicating that the array can reach the last subscript

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public boolean canJump(int[] nums) {
        int len = nums.length;
        int lastJump = len-1;   // The last subscript
        for (int i=len-2; i>-1; i--) {
            // Update the subscript if the last element can be reached
            if(nums[i] >= lastJump - i) { lastJump = i; }}return lastJump == 0;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {2.3.1.1.4};
        int[] nums1 = {3.2.1.0.4};
        boolean flag = new Number55().canJump(nums);
        System.out.println(flag);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥