Shulou(Shulou.com)06/03 Report--

This article introduces you how LeetCode realizes jumping games, the content is very detailed, interested friends can refer to it, I hope it can help you.

topic

Given an array of nonnegative integers, nums, you are initially at the first subscript of the array.

Each element in the array represents the maximum length you can jump at that position.

Determine if you can reach the last index.

Example 1: Input: nums = [2,3,1,1,4] Output: true

Explanation: You can jump 1 step from subscript 0 to subscript 1, and then jump 3 steps from subscript 1 to the last subscript.

Example 2: Input: nums = [3,2,1,0,4] Output: false

Explanation: No matter what, the subscript 3 will always be reached. But the maximum jump length for this index is 0, so it is never possible to reach the last index.

analysis

To reach the last subscript, two conditions must be met:

Assuming that every position can jump to, then we just need to traverse the array to see if there is a position that can jump directly to the end through the number at this position.

For example [2, 3, 2, 1, 4], we traverse the numbers to see which position can jump to the end, we can find that the number in the third position is 2, so we can jump to the last subscript through the third position, and the array is true.

2. Another condition for the above assumption is whether each position can jump to.

For example,[2, 0, 2, 1, 4], according to the above logic, the third position can jump to the last subscript. Can the third position be reached? If the third position is not reached, then what about the final position? In this example, the first position is 2, which can jump to the third position.

If you change it to [1, 0, 2, 1, 4], the third position will not be reached.

Combined with the above analysis, we can arrive at the following solution:

public boolean canJump(int[] nums) { //Maximum position k that can be reached int k =0; //traverse array for(int i=0;i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.