/来源：本人微信公众号：豫见成电
我会连载推送一些关于C语言，网络空间安全，数学建模，算法方面的学习经历，还有一些成电生活，欢迎大家关注。/
题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释:从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置
示例 2:
输入: [3,2,1,0,4]
输出: false
解释:无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。
解题思路：
根据题目描述，显然出现false的情况为有0时且无法跨越。当走到当前检索位置时，计算出下步可以到达的最大检索位置，遍历数组，如果当前位置计算的检索位置小于当前检索，则显然无法跨越，到最终如果大于等于最大检索，则返回true。
注意需要遍历数组，而不能模拟下步并进行跳跃。显然但是非常重要。
代码实现（C++）:
image
实现分析：
实现算法复杂度为O(n)。
/来源：本人微信公众号：豫见成电我会连载推送一些关于C语言，网络空间安全，数学建模，算法方面的学习经历，还有一些成...
leetcode刷题,使用python 1, 跳跃游戏 II —— 0045 贪心算法给定一个长度为 n 的 0...
demo4a：跳跃游戏（medium）----（贪心） 来源：leetcode 55 思路：找第一步能跳跃到的最远...
55. 跳跃游戏 相关标签 ： 数组， 贪心算法 1109. 航班预订统计 相关标签 ： 数组 数学
题目描述 考点 数组 贪心算法 解题思路 从头遍历数组，使用reach记录能够到达的最远位置；（1）如果当前遍历的...
写在前面 贪心算法说简单也简单，因为找到局部的最优解就可以了，说难也确实不是很好想，因为这种思想在想的时候总会有种...
LeetCode_55_Jump_Game 群里做题第一天，easy题 55. 跳跃游戏 题目内容是 给定一个非负...
Algorithm: 每周至少做一个 LeetCode 的算法题LeetCode 435 无重叠区间使用贪心算法解...
55. 跳跃游戏 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大...
LeetCode题目 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可跳跃的最大...
本文标题：贪心算法题：leetcode 55 跳跃游戏
本文链接：https://www.haomeiwen.com/subject/jkufxqtx.html
网友评论