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:

  1. LeetCode: 55. Jump Game
  2. Leetcode: 300. Longest Increasing Subsequence
  3. LeetCode: 560. Subarray Sum Equals K (find the sum of consecutive substrings in an array equal to k)

Article directory:

Topic description:

method 1:

java implementation method:

Python implementation method:

Method 2

java implementation method:

Python implementation method:

Source code github address: https://github.com/zhangyu345293721/leetcode


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:

  1. Input: [ 2 , 3 , 1 , 1 , 4 ]
  2. 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:

  1. Input: [ 3 , 2 , 1 , 0 , 4 ]
  2. 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.

The copyright belongs to Lingkou Network. For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.


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:

  1. /**
  2. * Jump game
  3. *
  4. * @param nums array
  5. * @return boolean
  6. */
  7. private boolean jumpGame1(int[] nums) {
  8. if (nums.length < 1) {
  9. return true;
  10. }
  11. int n = nums.length;
  12. int rightMost = 0;
  13. for (int i = 0; i < n; i++) {
  14. if (i <= rightMost) {
  15. rightMost = Math.max(rightMost, i + nums[i]);
  16. if (rightMost >= n - 1) {
  17. return true;
  18. }
  19. }
  20. }
  21. return false;
  22. }

Time complexity: O(n)

Space Complexity: O(1)


Python implementation method:

  1. def jump_game_1(nums: List[int]) -> bool:
  2. '''
  3. see if you can skip the array
  4. Args:
  5. nums: input array
  6. Returns:
  7. Boolean value
  8. '''
  9. max = 0
  10. length = len(nums)
  11. for index in range(1, length):
  12. if nums[index - 1] == 0 and index > nums[max] + max:
  13. return False
  14. if nums[max] - (index - max) < nums[index]:
  15. max = index
  16. 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:

  1. /**
  2. * Jump game
  3. *
  4. * @param nums array
  5. * @return boolean
  6. */
  7. public boolean canJump4(int[] nums) {
  8. if (nums.length == 1) {
  9. return true;
  10. }
  11. if (nums == null || nums[0] == 0) {
  12. return false;
  13. }
  14. for (int i = 0; i < nums.length - 1; i++) {
  15. if (nums[i] == 0) {
  16. boolean flag = jumpFlag(nums, i);
  17. if (flag) {
  18. continue;
  19. } else {
  20. return false;
  21. }
  22. }
  23. }
  24. return true;
  25. }
  26. /**
  27. * Determine whether to skip 0
  28. *
  29. * @param nums array
  30. * @param i position
  31. * @return boolean
  32. */
  33. private boolean jumpFlag(int[] nums, int i) {
  34. for (int j = i - 1; j >= 0; j--) {
  35. if (nums[j] > i - j) {
  36. return true;
  37. }
  38. }
  39. return false;
  40. }

Time complexity: O(n)

Space Complexity: O(1)


Python implementation method:

  1. def jump_game_2(self, nums: List[int]) -> bool:
  2. '''
  3. long jump array
  4. Args:
  5. nums: array
  6. Returns:
  7. Whether it can be adjusted to the end, boolean
  8. ''' ''
  9. if len(nums) < 2:
  10. return True
  11. if nums == None or arr[0] == 0:
  12. return True
  13. for i in range(len(nums)):
  14. if nums[i] == 0:
  15. flag = self.jump_flag(nums, i)
  16. if flag:
  17. continue
  18. else:
  19. return flag
  20. return True
  21. def jump_flag(self, nums: List[int], i: int) -> bool:
  22. '''
  23. Can you skip 0?
  24. Args:
  25. nums: array
  26. i: position i
  27. Returns:
  28. Boolean value
  29. '''
  30. j = i
  31. while j > 0:
  32. if nums[j] > i - j:
  33. return True
  34. j -= 1
  35. return False

Time complexity: O(n)

Space Complexity: O(1)


Source code github address:

https://github.com/zhangyu345293721/leetcode

Related: LeetCode: 55. Jump Game