题目链接

跳跃游戏

题目描述

image.png

实现代码

思路：首先，个人采用的dfs遍历，每次将能够到达的位置继续进行dfs遍历，直到能够到达最后一个下标的位置或者所有的遍历完都无法到达为止。实现代码如下（结果超时）：

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  4.         int len = nums.length;
  5.         if(len == 1) {
  6.             return true;
  7.         }
  9.         return canJump(nums, 0);
  10.     }
  12.     private boolean canJump(int[] nums, int startIdx) {
  14.         if(startIdx >= nums.length-1) {
  15.             return true;
  16.         }
  18.         int steps = nums[startIdx];
  20.         if(steps == 0) {
  21.             return false;
  22.         }
  24.         boolean result = false;
  25.         for(int i=1; i<= steps; i++) {
  26.             result |= canJump(nums, startIdx+i);
  27.         }
  29.         return result;
  31.     }
  32. }

官方题解：遍历数据nums，每次更新最远的距离位置，直到遍历完成或者能到达最后一个位置为止。实现代码如下：

  1. public class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int n = nums.length;
  4.         int rightmost = 0;
  5.         for (int i = 0; i < n; ++i) {
  6.             if (i <= rightmost) {
  7.                 rightmost = Math.max(rightmost, i + nums[i]);
  8.                 if (rightmost >= n - 1) {
  9.                     return true;
  10.                 }
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. }