当前位置：首页 > article >正文

【LeetCode】跳跃游戏ⅠⅡ 解题报告

article 2024/10/30 22:21:51

跳跃游戏 - 题目链接

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。

示例 1：

输入： $n u m s = [2, 3, 1, 1, 4]$
输出： $t r u e$
解释： 可以先跳 $1$ 步，从下标 $0$ 到达下标 $1$ ，然后再从下标 $1$ 跳 $3$ 步到达最后一个下标。

示例 2：

输入： $n u m s = [3, 2, 1, 0, 4]$
输出： $f a l se$
解释： 无论怎样，总会到达下标为 $3$ 的位置。但该下标的最大跳跃长度是 $0$ ，所以永远不可能到达最后一个下标。

提示：

$1 <= nums.length <= 10^4$
$0 <= nums[i] <= 10^5$

题目意思很简单，就是给你个数组，每个元素表示可以从当前位置往后移动至多多少位。举个例子，假如 $n u m s [0] == 2$ ，意思就是你可以从数组下标 $0$ 移动到 $0, 1, 2$ 任一位置。问能否最终从数组第一位移至最后一位 ~~（连通性？）~~。
刚拿到题我首先是想先打个爆搜试试的，结果不知道为什么本地 $I D E$ 测试数据能过，但是提交到 $O J$ 上之后就不行……总之把代码贴出来给大家看看。

inline bool CanJump(vector<int>& nums) {
	//本地能过OJ上不行
	static int Step = 0;
	if (Step == nums.size() - 1)return true;
	for (int i = 0; i < nums[Step]; ++i) {
		Step++;
		if (nums[Step])return CanJump(nums);
		Step--;
	}
	return false;
}

不过我想了想，就算过了样例，时间复杂度也是 $O(n^2)$ 数量级，还是可能寄。
为了想出一个时间复杂度为 $O (n)$ 的算法，我决定另辟蹊径，逆序遍历数组进行处理。
因为根据题意，若数组中没有 $0$ 出现，就一定可以从起点跳到终点，所以需要特殊处理的只有 $0$ 元素。当然，还有一些特殊情况需要考虑，例如 $n u m s . s i ze () == 1$ 或者 $0$ 元素位于终点。
详细思路讲解附在代码注释里：

class Solution {
public:
    bool canJump(vector<int>& nums) {
		int n = nums.size(), Zero_pos = -1;//记录0的位置
		for (int i = n - 1; i >= 0; --i) {
			if (!nums[i]) {
				Zero_pos = i;//找到第一个0所在位置，退出遍历
				break;
			}
		}
		if (Zero_pos < 0)return true;//如果没有0，一定可以到达终点
		else if (!Zero_pos)return n < 2;//如果nums[0]=0，则只需判断数组大小是否为1即可
		else {//否则需要继续处理
			bool flag = false;//标记
			for (int i = Zero_pos; i >= 0; --i) {
				if (Zero_pos == n - 1 && Zero_pos - i <= nums[i])flag = true;
				//如果0位于终点，则影响不大，只要前面有能到达终点的元素就可以
				else if (Zero_pos - i < nums[i])flag = true;
				//否则，如果要越过当前0所在位置，则前面必须有元素的值大于0到它的距离
				if (!nums[i] && flag)Zero_pos = i, flag = false;
				//如果这个0已经越过，且又出现0，则更新0位置下标，以及重新把flag置false
			}
			return flag;
		}
    }
};

完整代码也可看我的Github：传送门

可以看到时间和空间消耗都很低，还是不错的。
趁热打铁，来看看跳跃游戏Ⅱ。

跳跃游戏 II - 题目链接

给定一个长度为n的 $0$ 索引 整数数组nums。初始位置为nums[0]。

每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:

$0 <= j <= n u m s [i]$
$i + j < n$

返回到达nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。

示例 1：

输入： $n u m s = [2, 3, 1, 1, 4]$
输出： $2$
解释： 跳到最后一个位置的最小跳跃数是2。
从下标为 $0$ 跳到下标为 $1$ 的位置，跳1步，然后跳3步到达数组的最后一个位置。

示例 2：

输入： $n u m s = [2, 3, 0, 1, 4]$
输出： $2$

提示：

$1 <= nums.length <= 10^4$
$0 <= n u m s [i] <= 1000$
题目保证可以到达nums[n-1]

幽默题目描述。
用人话翻译一下，给你个和跳跃游戏Ⅰ一样的数组，然后求从数组第一位到最后一位要跳的最少步数。
这题可以用贪心做，但是众所周知，贪心容易翻车。我的习惯是先打暴力模拟，模拟不出来再搜索，搜索不出来再尝试思考正经算法，想不出来最后才用贪心。
这题，显然动态规划比较合适。
当然， $d p$ 之中亦有三六九等，先拉下等马出来遛遛。

class Solution {
public:
    int jump(vector<int>& nums) {
		int n = nums.size();
		vector<int>dp(n, 0x3f3f3f3f);//初始赋一个极大值
		if (!nums[0] || n < 2)return 0;//如果起点就是0或者数组元素只有一个就不用跳了
		dp[0] = 0;//初始化
		for (int i = 1; i < n; ++i)
			for (int j = 0; j < i; ++j)
				if (i - j <= nums[j])dp[i] = min(dp[i], dp[j] + 1);//状态转移方程
		return dp[n - 1];
    }
};