跳跃游戏
今天的题目是力扣面试经典150题中的数组的中等难度题:跳跃游戏。
题目链接:https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150
题目描述
给定一个非负整数数组 nums,你最初位于数组的 第一个下标,即 nums[0] 。数组中的每个元素代表一个障碍的高度。
你想要到达最后一个下标,但是除了从下标 i 跳到下标 i + nums[i] 之外,你不能跳过任何下标。
确定你是否能够到达最后一个下标。
-
示例 1:
- 输入: [2,3,1,1,4]
- 输出: true
-
示例 2:
- 输入: [3,2,1,0,4]
- 输出: false
题目分析
题目要求我们判断在一个障碍高度数组中,从起点能否跳到最后一个位置。
题目的意思就是给定一个数组,我们从数组的第一个下标位置开始,根据下标元素的值x,我们可以向前移动下标,移动区间为(1,x]。如果当下下标的值是0,那么将无法向前移动,这个时候跳跃游戏结束,结束时所在下标如果不是最后一个下标,就返回false。
解题思路
这种情况我们可以直接考虑贪心算法,就是每次都走最大步,看看能不能出去游戏。
首先我们定义一个最大移动距离,初始值时0,因为还没有开始移动。
开始进行循环,从第一个元素开始。
当第一个值时0且长度大于1时,可以直接返回,因为无法移动。
定义结束条件,当你最大移动的距离小于当前下标的值,说明你已经无法移动了,可以直接返回false。
下面我们需要更新最大距离。在每次都走最大步长的情况下,最大距离就等于下标的值加上元素的值,这个时候与当前的距离取大即可。
最后看看如果当前最大距离已经超过了数组长度,说明已经到了终点,返回true。
实际算法代码
以下是使用上述思路的 Java 实现:
public class JumpGame {
public static void main(String[] args) {
JumpGame solution = new JumpGame();
int[] nums1 = {2, 3, 1, 1, 4};
int[] nums2 = {3, 2, 1, 0, 4};
System.out.println(solution.canJump(nums1)); // 输出: true
System.out.println(solution.canJump(nums2)); // 输出: false
}
public boolean canJump(int[] nums) {
int maxReach = 0;
if (nums.length == 1) {
return true;
}
for (int i = 0; i < nums.length; i++) {
if (nums.length > 1 && num[i] == 0) {
return false;
}
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) {
return true;
}
}
return maxReach >= nums.length - 1;
}
}
结果
执行程序,测试通过:
提交到力扣,也通过,并且表现不错。
总结
又是使用贪心算法的一天。这个题目和股票买卖的有一个共同点,也是常见使用贪心算法的场景。那就是通过局部的最优解进而实现整体的最优解。
在股票买卖中,我们通过每次都能获取利润从而获取最大的利润,在今天的跳跃游戏中,我们每次都走最远从而跳出数组。学会从题目归纳场景,在用场景归纳出解题思路,这是刷算法要得到的收获,不是做完题目就行,归纳总结,这是才是正经学习!
加油!!!
标签:150,下标,nums,maxReach,力扣,面试,数组,题目,false From: https://blog.csdn.net/weixin_48668564/article/details/141376243