【Hot100】LeetCode—45. 跳跃游戏 II

---

• 原题链接：45. 跳跃游戏 II

---

1- 思路

覆盖范围

• int cur = 0 ：记录当前的覆盖范围
• int next = 0：记录当前结点最远的跳跃距离
• int res = 0：记录具体跳几步

覆盖范围更新：

• 1- 如果 i == cur 也就是说当前结点 i 的下标等于 cur，i 已经到达了覆盖范围能跳的最远距离，则需要进行下一跳
  • 下一跳之前，要判断是否到达终点
  • 若未到达终点，则进行下一跳

---

2- 实现

⭐45. 跳跃游戏 II——题解思路

class Solution {public int jump(int[] nums) {int curCover = 0;int nextCover = 0;int res = 0;for(int i = 0 ; i< nums.length;i++){nextCover = Math.max(nextCover,i+nums[i]);if(curCover == i){if(i != nums.length-1){res++;curCover = nextCover;}}}return res;}
}

---

3- ACM 实现

public class jump2 {public static int jump2(int[] nums){int curCover = 0;int nextCover = 0;int res =0;for(int i = 0 ; i < nums.length;i++){nextCover = Math.max(nextCover,i+nums[i]);if(i == curCover){if(i != nums.length-1){curCover = nextCover;res++;}}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();String[] parts = input.split(" ");int[] nums = new int[parts.length];for(int i = 0 ; i < parts.length;i++){nums[i] = Integer.parseInt(parts[i]);}System.out.println("结果是"+jump2(nums));}}