java数据结构与算法刷题-----LeetCode55. 跳跃游戏

本文主要是介绍java数据结构与算法刷题-----LeetCode55. 跳跃游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

解题思路：时间复杂度O($n$)，空间复杂度O($1$)

1. 依次遍历数组，记录我们能到达的最远位置
2. 如果最远位置可以到达终点，就返回true，否则返回false

可以利用的细节

1. 我们当前最远可达距离之内的任意数组元素，都可以作为下一个跳板
2. 所以我们要不断观察可达距离之内的元素，是否踏上它可以跳的更远，从而扩大最远可达距离

代码

public class Solution {public boolean canJump(int[] nums) {int n = nums.length;//数组长度int rightmost = 0;//最远能走到多远for (int i = 0; i < n; ++i) {if (i <= rightmost) {//如果当前位置，还不到我们目前能到达的最远距离，都是我们可以跳跃的位置rightmost = Math.max(rightmost, i + nums[i]);//如果当前位置i，能让我们走的更远，记录目前能到达最远距离if (rightmost >= n - 1) return true;//如果最远距离能到终点，就返回true  }}return false;}
}

这篇关于java数据结构与算法刷题-----LeetCode55. 跳跃游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---