网站广东海外建设集团有限公司,十个有趣又好玩的网页,平面设计线下培训班多少钱,网站建设化学图片55. 跳跃游戏
labuladong 题解思路
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返…55. 跳跃游戏
labuladong 题解思路
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
**输入**nums [2,3,1,1,4] **输出**true **解释**可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2
**输入**nums [3,2,1,0,4] **输出**false **解释**无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
提示
1 nums.length 1040 nums[i] 105
题解
这个问题可以通过贪心算法来解决。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法。对于跳跃游戏问题我们可以采用以下策略 初始化最远距离设置一个变量来存储在遍历数组过程中能够到达的最远距离初始时这个最远距离为0。 遍历数组遍历数组中的每个元素对于每个元素执行以下操作 更新最远距离对于当前位置i它能够到达的最远距离至少是i nums[i]因此更新最远距离为max(当前最远距离, i nums[i])。判断能否继续向前如果当前位置i大于最远距离则说明无法从起点跳到当前位置因此返回false。 判断能否到达终点如果能够遍历完整个数组则表示可以到达终点返回true否则返回false。
下面是该算法的C实现
#include vector
using namespace std;bool canJump(vectorint nums) {int maxReach 0;for (int i 0; i nums.size(); i) {if (i maxReach) return false;maxReach max(maxReach, i nums[i]);if (maxReach nums.size() - 1) return true;}return (maxReach nums.size() - 1);
}这段代码首先判断当前位置是否可达然后更新最远可达距离。如果在某个位置发现该位置已经超出了之前能够达到的最远位置则表明无法到达数组的最后位置。
在这个问题中我们假设至少有一个位置可以被到达即起始位置因此算法至少会执行一次循环。如果能够遍历完整个数组则意味着可以从起始位置跳到数组的最后位置。
45. 跳跃游戏 II
labuladong 题解思路
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i]i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums [2,3,0,1,4] 输出: 2
提示:
1 nums.length 1040 nums[i] 1000题目保证可以到达 nums[n-1]
题解
贪心
在“跳跃游戏 II”问题中我们可以使用贪心算法来找到到达数组末尾的最小跳跃次数。这个问题的核心是在每一步中做出最优选择即在当前能跳到的所有位置中选择一个能使得从这个位置开始能跳到的最远位置的点。
以下是用贪心算法解决这个问题的思路 初始化设置当前能到达的最远位置 maxReach、当前跳跃的结束位置 end 和跳跃次数 jumps。 遍历数组遍历数组中的每一个元素并更新当前能到达的最远位置 maxReach。 更新跳跃次数和跳跃结束位置当遍历到当前跳跃的结束位置时意味着需要进行一次新的跳跃除非已经到达数组末尾。此时更新跳跃次数并将跳跃结束位置设置为当前能到达的最远位置。 返回结果遍历完数组后返回跳跃次数作为结果。
以下是这个贪心算法的 C 实现
class Solution {
public:int jump(vectorint nums) {int maxReach 0, end 0, jumps 0;int n nums.size();for (int i 0; i n - 1; i) {maxReach max(maxReach, i nums[i]);if (i end) {jumps;end maxReach;}}return jumps;}
};这个算法的时间复杂度是 O(n)其中 n 是数组 nums 的长度。这比动态规划的方法更高效因为它避免了不必要的重复计算。
