坑
多测试用例，尽量不要使用静态变量，后台的测试方法，可能会保存之前存在的静态变量的值！！！最终，导致你的结果出错。
目录
坑
题目链接：55. 跳跃游戏 - 力扣（LeetCode）
题目描述
解法一：递归
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
解法二：动态规划
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
解法三：贪心
贪心算法思路
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
总结
题目链接：55. 跳跃游戏 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个非负整数数组 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 <=0 <= nums[i] <=
解法一：递归
-
主函数
canJump(int[] nums)：- 调用辅助函数
continueGo(nums, 0)开始递归处理，从数组的第一个元素（索引为0）开始尝试能否跳到最后一个位置。
- 调用辅助函数
-
辅助函数
continueGo(int[] nums, int pos)：- 首先检查当前位置
pos是否已经到达或超过了数组的最后一个位置，如果是，则返回true表示成功。 - 获取当前位置允许跳跃的最大步数
maxStep = nums[pos]。 - 如果在当前位置不能向前跳跃（即
maxStep == 0），则直接返回false。 - 检查如果从当前位置跳跃最大步数可以直接到达或超过数组的最后一个位置，若是，也直接返回
true。 - 使用循环从1到
maxStep（包括maxStep），递归调用continueGo(nums, pos + i)来模拟从当前位置跳跃i步后的状态。只要有一次跳跃能到达终点，就立即返回true。 - 如果所有可能的跳跃都不能到达终点，则最终返回
false。
- 首先检查当前位置
Java写法：
class Solution {public boolean canJump(int[] nums) {return continueGo(nums, 0);}private boolean continueGo(int[] nums, int pos) {int len = nums.length;// 如果位置已经到达或者是超过最后一个位置那么肯定就是true了if (pos >= len - 1) {return true;}int maxStep = nums[pos];// 中途出现了0，肯定是falseif (maxStep == 0) {return false;}// 如果当前能够“一步登天”的话，返回trueif (pos + maxStep >= len - 1) {return true;}// for (int i = maxStep; i >= 1; i--) {for (int i = 1; i <= maxStep; i++) {if (continueGo(nums, pos + i)) {return true;}}return false;}
}C++写法：
class Solution {
public:bool canJump(vector<int>& nums) {return continueGo(nums, 0);}private:bool continueGo(const vector<int>& nums, int pos) {int len = nums.size();// 如果位置已经到达或者是超过最后一个位置那么肯定就是true了if (pos >= len - 1) {return true;}int maxStep = nums[pos];// 中途出现了0，肯定是falseif (maxStep == 0) {return false;}// 如果当前能够“一步登天”的话，返回trueif (pos + maxStep >= len - 1) {return true;}for (int i = 1; i <= maxStep; ++i) {if (continueGo(nums, pos + i)) {return true;}}return false;}
};运行时间
时间复杂度和空间复杂度
由于其递归的本质，只要数据量够大就从根本上扼杀了它能够成功AC的可能了。
解法二：动态规划
利用一个dp数组记录每个位置是否可达（1表示可达，0表示不可达）。具体步骤如下：
-
初始化：
dp[0] = 1：起点默认是可达的。- 如果起点处的最大跳跃步数为0且数组长度大于1，则直接返回
false，因为无法进行任何跳跃。
-
遍历整个数组：
- 对于每一个位置
i，首先检查它是否可达（即dp[i] == 1），如果当前位置不可达，则直接返回false，因为后续的位置也不可能通过该点到达。 - 计算从当前位置最多可以跳多远（
maxStep = nums[i]）。 - 如果从当前位置可以直接到达或超过最后一个位置，则立即返回
true。 - 标记从当前位置出发可到达的所有位置为可达（在
dp数组中将这些位置设置为1）。
- 对于每一个位置
-
最终判断：
- 遍历结束后，检查终点位置是否可达（即
dp[len - 1] == 1），并据此返回结果。
- 遍历结束后，检查终点位置是否可达（即
Java写法：
class Solution {public boolean canJump(int[] nums) {int len = nums.length;// dp[]数组记录每个位置是不是可以到达int[] dp = new int[len];// 第一个位置判断if(nums[0] == 0 && len > 1){return false;}dp[0] = 1;for(int i = 0; i < len - 1; i++){// 当前最多可以跳多远int maxStep = nums[i];// 先判断当前位置是否是可以到达的，if(dp[i] == 0){return false;}// 如果可以一步到位就直接返回trueif(maxStep + i >= len - 1){return true;}// 然后标记这些已经可以跳跃到达的地方为1for(int j = i + 1; j <= maxStep + i; j++){dp[j] = 1;}}// 那么数组中可以到达的地方已经被标记为1了，如果最终是不可达的，那么数组的最后一位就是0return dp[len - 1] == 1? true : false;}
}C++写法：
#include <vector>
using namespace std;class Solution {
public:bool canJump(vector<int>& nums) {int len = nums.size();vector<int> dp(len, 0); // 初始化dp数组，默认所有位置都不可达if(nums[0] == 0 && len > 1) { // 起点不能前进的情况return false;}dp[0] = 1; // 起点默认可达for(int i = 0; i < len - 1; ++i) {if(dp[i] == 0) { // 当前位置不可达return false;}int maxStep = nums[i]; // 当前最大跳跃步数if(i + maxStep >= len - 1) { // 可以一步到位return true;}// 标记从当前位置出发可到达的所有位置为可达for(int j = i + 1; j <= i + maxStep && j < len; ++j) {dp[j] = 1;}}// 判断终点是否可达return dp[len - 1] == 1;}
};运行时间
时间复杂度和空间复杂度
- 时间复杂度：O(
)。这是因为在最坏情况下，对于每个元素，你都需要遍历它之后的所有元素来更新它们的状态。
- 空间复杂度：O(
)。主要是由于额外的
dp数组用来存储每个位置是否可达的信息。
解法三：贪心
贪心算法可以在 O(n) 时间和 O(1) 空间内解决。我们可以通过维护一个当前能到达的最远位置来判断是否能到达终点。
贪心算法思路
-
初始化最远位置：用变量
max_reach记录当前能跳跃到的最远位置。 -
遍历数组：对每个位置
i：-
如果
i超出了max_reach，说明无法到达当前位置，直接返回false。 -
否则，更新
max_reach = max(max_reach, i + nums[i])。 -
如果
max_reach已经能到达终点，提前返回true。
-
-
最终判断：遍历结束后，若
max_reach能覆盖终点则成功。
Java写法：
class Solution {public boolean canJump(int[] nums) {int maxReach = 0;int len = nums.length;for (int i = 0; i < len; i++) {// 关键：先检查是否可达if (i > maxReach){return false} maxReach = Math.max(maxReach, i + nums[i]);// 提前终止if (maxReach >= len - 1){return true；}}return true;}
}C++写法：
#include <vector>
#include <algorithm> // 用于std::max
using namespace std;class Solution {
public:bool canJump(vector<int>& nums) {int maxReach = 0;int len = nums.size();for (int i = 0; i < len; ++i) {// 关键：先检查是否可达if (i > maxReach) {return false; // 注意这里加上了缺失的分号}maxReach = max(maxReach, i + nums[i]); // 使用std::max// 提前终止if (maxReach >= len - 1) {return true; // 修正了这里的中文分号为英文分号}}return true;}
};运行时间
时间复杂度和空间复杂度
总结
这篇博客写了我足足一下午，困呐困呐困呐，今天的天也变成了绿色。嘿嘿嘿
