45. 跳跃游戏 II

本文主要是介绍45. 跳跃游戏 II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

链接

45. 跳跃游戏 II - 力扣（LeetCode） (leetcode-cn.com)

解法：贪心

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

 1 class Solution {
 2     public int jump(int[] nums) {
 3         if (nums == null || nums.length == 0 || nums.length == 1) {
 4             return 0;
 5         }
 6         //记录跳跃的次数
 7         int count=0;
 8         //当前的覆盖最大区域
 9         int curDistance = 0;
10         //最大的覆盖区域
11         int maxDistance = 0;
12         for (int i = 0; i < nums.length - 1; i++) {
13             maxDistance = Math.max(maxDistance, i + nums[i]);
14             if(maxDistance >= nums.length - 1) {
15                 count++;
16                 break;
17             }
18             //走到当前覆盖的最大区域时，更新下一步可达的最大区域
19             if (i == curDistance) {
20                 count++;
21                 curDistance = maxDistance;
22             }
23         }
24         return count;
25     }
26 }

参考

代码随想录 (programmercarl.com)

这篇关于45. 跳跃游戏 II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！