每天一道算法题之跳跃游戏
程序员文章站
2022-09-25 08:17:01
题目描述:给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。1分析:通过一个变量reach记录当前位置可以到达的最远位置,并将这个最远位置与数组最后一个位置进行比较,如果可以到达最后一个位置,返回true,反之无法到达,其变形题求的是通过几部可以到达数组最后,那么每更新一次reach就完成了一步代码部分:public boolean canJump(int[] nums) { if(nums....
题目描述:
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。1
-
分析:
通过一个变量reach记录当前位置可以到达的最远位置,并将这个最远位置与数组最后一个位置进行比较,如果可以到达最后一个位置,返回true,反之无法到达,其变形题求的是通过几部可以到达数组最后,那么每更新一次reach就完成了一步
-
代码部分:
public boolean canJump(int[] nums) {
if(nums.length < 2) return true;
//解题的关键;将最远能到达的位置与nums.length进行比较
int reach = 0,i = 0;
for(;i<nums.length && i<=reach;i++){ //i要满足两个条件
reach = Math.max(reach,nums[i] + i); //更新可到达的最远的范围
if(reach>= nums.length-1) return true; //判断最远范围是否超过数组长度
}
return false;
}
-
https://leetcode-cn.com/problems/jump-game/ ↩︎
本文地址:https://blog.csdn.net/m0_46855873/article/details/107620364
推荐阅读
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
每天一道算法题系列五之最长回文子串
-
每天一道算法题之跳跃游戏
-
【Python刷题Leetcode】贪心算法(分糖果、摇摆序列、移除K个数、跳跃游戏、射击气球、加油次数)
-
每天一道算法题系列五之最长回文子串
-
每天一道算法题之跳跃游戏
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
【Python刷题Leetcode】贪心算法(分糖果、摇摆序列、移除K个数、跳跃游戏、射击气球、加油次数)