LeetCode热题100--45. 跳跃游戏 II--中等

题目

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

题解

classSolution{publicintjump(int[]nums){intans=0;intcurRight=0;// 已建造的桥的右端点intnextRight=0;// 下一座桥的右端点的最大值for(inti=0;i<nums.length-1;i++){// 遍历的过程中，记录下一座桥的最远点nextRight=Math.max(nextRight,i+nums[i]);if(i==curRight){// 无路可走，必须建桥curRight=nextRight;// 建桥后，最远可以到达 next_rightans++;}}returnans;}}

解析

出自：【图解】一张图秒懂跳跃游戏！（Python/Java/C++/C/Go/JS/Rust）

classSolution{//定义一个新的解决方案类publicintjump(int[]nums){//整型方法jump输入一个整型数组nums，用于找到到达最后一个索引所需的最小跳跃次数intans=0;//初始化变量ans（存储步数）为零。它将用于跟踪总共需要的跳跃次数intcurRight=0,nextRight=0;//初始化当前最右位置curRight和下一座桥（或可以到达的位置）nextRight为0。用于计算我们当前步数内可以到达的最大点for(inti=0;i<nums.length-1;i++){//循环遍历整个数组，直到不是最后一个元素（长度-1）//记录下一座桥的最远点nextRight=Math.max(nextRight,i+nums[i]);//将变量nextRight更新为旧的nextRight和当前位置加上我们通过步数可以到达的最大距离之间的较大值。这样确保了我们总是选择一个尽量靠右的位置（因为下一座桥越远）if(i==curRight){//如果在当前点无法继续向前，必须要跳跃到该点curRight=nextRight;//将当前最右位置更新为next_right。这表示我们可以到达下一个桥/步数的最远点ans++;//增加步数计数器（ans），因为我们需要走过这个距离来达到我们的新右端点}}//当我们走过了整个数组但无法跨越最后一个元素时，返回步数。这表示我们必须再跳一次以到达最后一个元素returnans;//返回总共步数（ans）的数量，它是最短路径的问题。时间复杂度为O(n)，空间复杂度为O(1)，其中n是输入数组nums的大小