【算法与数据结构】LeetCode55、45、跳跃游戏 I 、II

本文主要是介绍【算法与数据结构】LeetCode55、45、跳跃游戏 I 、II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、跳跃游戏I
二、跳跃游戏II
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、跳跃游戏I

在这里插入图片描述

思路分析：本题目标是根据跳跃数组的元素，判断最终能够到达数组末端。我们引入了一个跳跃范围的概念，代表当前能够跳得到的地方，不断跟新跳跃范围，如果跳跃范围能够大于数组长度-1，说明能够到达终点。计算第一个覆盖范围，然后基于第一个覆盖范围遍历[0,cover]内的所有跳跃步数，更新跳跃范围。用到algorithm头文件中的max函数。
程序如下：

// 55、跳跃游戏1
class Solution {
public:bool canJump(vector<int>& nums) {if (nums.size() == 1) return true;int cover = 0;		for (int i = 0; i <= cover; i++) {cover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true;}return false;}
};

复杂度分析：

时间复杂度： $O (n)$ 。
空间复杂度： $O (1)$ 。

二、跳跃游戏II

在这里插入图片描述

思路分析：跳跃游戏II在I的基础之上需要找到到达终点的最小步数。因此，我们走的每一步都需要仔细思考，保证到达终点的步数最小。程序当中，我们计算的下一步最大覆盖范围和当前覆盖范围，遇到i=cover的情况时更新当前覆盖范围，走下一步，并判断是否到达终点。
程序如下：

// 45、跳跃游戏2
class Solution2 {
public:int jump(vector<int>& nums) {// 统计覆盖范围和下一步最大覆盖范围（循环更新）if (nums.size() == 1) return 0;int cover = 0, next_cover = 0;int result = 0;	for (int i = 0; i < nums.size(); i++) {next_cover = max(nums[i] + i, next_cover);  // 更新下一步覆盖最远距离下标if (i == cover) {							// 遇到当前覆盖最远距离下标result++;                               // 需要走下一步cover = next_cover;						// 更新当前覆盖最远距离下标if (next_cover >= nums.size() - 1) break;  // 到达终点}}return result;}
};

复杂度分析：

时间复杂度： $O (n)$ 。
空间复杂度： $O (1)$ 。

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;// 55、跳跃游戏1
class Solution {
public:bool canJump(vector<int>& nums) {if (nums.size() == 1) return true;int cover = 0;		for (int i = 0; i <= cover; i++) {cover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true;}return false;}
};// 45、跳跃游戏2
class Solution2 {
public:int jump(vector<int>& nums) {// 统计覆盖范围和下一步最大覆盖范围（循环更新）if (nums.size() == 1) return 0;int cover = 0, next_cover = 0;int result = 0;	for (int i = 0; i < nums.size(); i++) {next_cover = max(nums[i] + i, next_cover);  // 更新下一步覆盖最远距离下标if (i == cover) {							// 遇到当前覆盖最远距离下标result++;                               // 需要走下一步cover = next_cover;						// 更新当前覆盖最远距离下标if (next_cover >= nums.size() - 1) break;  // 到达终点}}return result;}
};int main() {//vector<int> nums = { 2,3,1,1,4 };//Solution s1;//bool result = s1.canJump(nums);//cout << result << endl;//system("pause");//return 0;//vector<int> nums = { 2,3,1,1,4 }; // 2步，统计一次下一步最大覆盖范围vector<int> nums = { 1,2 };		// 1步，没有统计，cover就满足了//vector<int> nums = { 0 };Solution2 s2;int result = s2.jump(nums);cout << result << endl;system("pause");return 0;
}