## LeetCode: 55. Jump Game

The first article : I am Octopus, the name comes from my Chinese name - octopus; I love programming, algorithms, and open source. All the source code is in my personal github  ; this blog is to record the bits and pieces of my learning, if you are interested in Python, Java, AI, and algorithms, you can follow my news, learn together, and make progress together.

related articles:

Article directory:

Topic description:

method 1:

java implementation method:

Python implementation method:

Method 2

java implementation method:

Python implementation method:

### Topic description:

Given an array of non-negative integers , you are initially at the first position 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 position.

Example 1:

``Input: [ 2 , 3 , 1 , 1 , 4 ]output: true``

Explanation: We can jump 1 step, from position 0 to position 1, and then jump 3 steps from position 1 to the last position.
Example 2:

``Input: [ 3 , 2 , 1 , 0 , 4 ]output: false``

Explanation: No matter what, you will always reach the position at index 3. But the maximum jump length for that position is 0, so you can never get to the last position.

## method 1:

We can solve this problem in a greedy way.

Imagine, for any position y in the array, how can we tell if it is reachable? According to the description of the title, as long as there is a position x, it can be reached by itself, and the maximum length of its jump is x + nums[x], this value is greater than or equal to y, that is, x + nums[x]≥y, then the position y is also can be reached. In other words, for each reachable position x, it makes the consecutive positions x+1, x+2, ,⋯,x+nums[x] reachable. In this way, we traverse each position in the array in turn, and maintain the furthest reachable position in real time. For the current traversed position x, if it is within the range of the farthest reachable position, then we can reach this position by several jumps from the starting point, so we can update the farthest reachable position with x + nums[x] s position. In the process of traversing, if the farthest reachable position is greater than or equal to the last position in the array, it means that the last position is reachable, and we can directly return True as the answer. Conversely, if the last position is still unreachable after the traversal is over, we return False as the answer. Take example 1 in the title: [2, 3, 1, 1, 4] as an example: we start at position 0, and the maximum length that can be jumped is 2, so the farthest position that can be reached is updated to 2; we traverse To position 1, since 1≤2, position 1 is reachable. We add 1 to the maximum length it can jump, 3, and update the furthest position it can reach to 4. Since 4 is greater than or equal to the last position 4, we simply return True.

Let's take a look at the second example in the title: [3, 2, 1, 0, 4] We start at position 0, and the maximum length that can be jumped is 3, so the farthest position that can be reached is updated to 3; we traverse To position 1, since 1≤3, position 1 is reachable, plus the maximum length 2 it can jump to get 3, which does not exceed the farthest reachable position; the same is true for position 2 and position 3, the farthest reachable position will not be updated; we traverse to position 4, and since 4 > 3, position 4 is unreachable, and we ignore the maximum length it can jump. After the traversal is complete, position 4 is still unreachable, so we return False.

### java implementation method:

``   /**     * Jump game     *     * @param nums array     * @return boolean     */    private boolean jumpGame1(int[] nums) {        if (nums.length < 1) {            return true;        }        int n = nums.length;        int rightMost = 0;        for (int i = 0; i < n; i++) {            if (i <= rightMost) {                rightMost = Math.max(rightMost, i + nums[i]);                if (rightMost >= n - 1) {                    return true;                }            }        }        return false;    }``

Time complexity: O(n)

Space Complexity: O(1)

### Python implementation method:

``def jump_game_1(nums: List[int]) -> bool:        '''            see if you can skip the array        Args:            nums: input array        Returns:            Boolean value        '''        max = 0        length = len(nums)        for index in range(1, length):            if nums[index - 1] == 0 and index > nums[max] + max:                return False            if nums[max] - (index - max) < nums[index]:                max = index        return True``

Time complexity: O(n)

Space Complexity: O(1)

## Method 2

According to the title, it can be concluded that when you go through 0 no matter how you jump, that is, when 0 is your only way, you cannot jump out of the array. So as long as you find a path that can jump out of 0, you can jump to the last bit. So how to judge whether it can jump out of 0? Set the current index of 0 as index, use i to traverse index-1 to 0, and find a number greater than index-i to jump out of 0

### java implementation method:

``   /**     * Jump game     *     * @param nums array     * @return boolean     */    public boolean canJump4(int[] nums) {        if (nums.length == 1) {            return true;        }        if (nums == null || nums == 0) {            return false;        }        for (int i = 0; i < nums.length - 1; i++) {            if (nums[i] == 0) {                boolean flag = jumpFlag(nums, i);                if (flag) {                    continue;                } else {                    return false;                }            }        }        return true;    }     /**     * Determine whether to skip 0     *     * @param nums array     * @param i position     * @return boolean     */    private boolean jumpFlag(int[] nums, int i) {        for (int j = i - 1; j >= 0; j--) {            if (nums[j] > i - j) {                return true;            }        }        return false;    }``

Time complexity: O(n)

Space Complexity: O(1)

### Python implementation method:

``    def jump_game_2(self, nums: List[int]) -> bool:        '''             long jump array        Args:            nums: array        Returns:            Whether it can be adjusted to the end, boolean        ''' ''        if len(nums) < 2:            return True        if nums == None or arr == 0:            return True        for i in range(len(nums)):            if nums[i] == 0:                flag = self.jump_flag(nums, i)                if flag:                    continue                else:                    return flag        return True    def jump_flag(self, nums: List[int], i: int) -> bool:        '''            Can you skip 0?        Args:            nums: array            i: position i        Returns:            Boolean value        '''        j = i        while j > 0:            if nums[j] > i - j:                return True            j -= 1        return False``

Time complexity: O(n)

Space Complexity: O(1)