赞
踩
给定一个数组,每一个位置的数字,表示当前位置能跳跃的最大步数。你起始位于 index = 0 的位置,判断你是否能够跳跃到最后一个位置。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
原题链接: https://leetcode-cn.com/problems/jump-game/
动态规划思路:不妨从后往前,先找到第一个能跳到最后一个位置的位置,我们称之为可行的位置。例如,[2, 3, 1, 1, 4],对于倒数第 2 个位置,其到达末尾的距离为 1,其步数为 1, 所以倒数第 2 个位置是一个可行的位置。那么问题又变成了子问题:从 index = 0 出发,能否到达 倒数第 2 个位置,即 [2, 3, 1, 1] 是否是一个可跳跃到结尾的数组。然后重复从后往前的遍历,直到回到 index = 0 为止,判断其是否是一个可行的位置。
这里 distance[i] 定义为当前位置到达下一个可行点的距离。
转移方程可以理解为 distance[i - 1] = 1 if nums[i - 1] >= distance[i] else distance[i] + 1。初始化 distance[end] = 0
贪心思路:假设有坐标 x 和 y,如果满足 x + nums[x] >= y,则我们除了可以达到坐标 y 之外,还可以到达 x+1,x+2,…,x+nums[x]。这些点都是我们可以遍历的点。那么我们可以从前往后遍历,记录当前位置能到达的最右坐标, 只要还在能到达的最右坐标以内,我们都可以一直往后走,并不停更新最右坐标。直到走到最后一个位置为止。如果遍历到最右坐标,却走不动了,则提前退出,返回结果。
class Solution { public: bool canJump(vector<int>& nums) { int distance = 0; int last_index = nums.size(); for (int i = nums.size() - 1; i >= 0; i--) { if (nums[i] >= distance) { distance = 0; } if (i == 0 && distance == 0) { return true; } distance++; } return false; } };
class Solution {
public:
bool canJump(vector<int>& nums) {
int rightMaxIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > rightMaxIndex) {
return false;
}
rightMaxIndex = max(rightMaxIndex, i + nums[i]);
}
return true;
}
};
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。