likes
comments
collection
share

LeetCode第55题跳跃游戏

作者站长头像
站长
· 阅读数 17

继续打卡算法题,今天学习的是LeetCode第55题跳跃游戏,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

LeetCode第55题跳跃游戏

分析一波题目

我们只要把当前时刻可以到达的最大位置保存下来,每次判断当前位置是否可以到达,或者当前位置是否可以到达最后的位置。 这个思路就是先求局部最优的解,然后根据局部最优的解可以推导出全局最优解。

[2,3,1,1,4] 为例子

第1次遍历到位置1,此刻最大可以到达下标(0+2)=2

第2次遍历到位置2,此刻位置可以到达,且当前位置可以最大可以到达下标(1+3)=4的位置,

第3次遍历到位置3,此刻位置可以到达,且当前位置可以到达的下标(2+1)=3位置,这个时候发现,前面位置可以到达的位置更远

第4次遍历到位置4,此刻位置可以到达,且当前位置可以到达下标(1+3)位置,此刻发现已经到达了末尾位置

本题解题技巧

本题巧妙的地方就在于把当前位置最大可以到的下标记录下来,

注意我们不要纠结当前位置该跳跃几步,而是判断当前位置是否可以到达,并且当前位置可以继续往前跳。如果这两个条件都满足,我们就一直往前跳,直到到达末尾位置。

编码解决

class Solution {
    public boolean canJump(int[] nums) {
      // write code here
      int reach = 0; // 目前最远能跳到的点
      for (int i = 0; i < nums.length; i++) {
        // 之前的点都跳不到当前的点,所以失败
        if (reach < i) return false;
        // 已经能跳到最后一个点了,直接返回
        if (reach >= nums.length-1) return true;
        // 如果通过当前的点能够到更远的点,更新reach
        reach = Math.max(reach, i + nums[i]);
      }
        
      return true;
    
    }
}

总结

相比第45题跳跃游戏II, 本题更好理解,我们只要想到判断每个位置是否可以继续往下跳的思路,就可以解决此题。

转载自:https://juejin.cn/post/7289661052808036410
评论
请登录