欢迎访问LeetCode题解合集
题目描述
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
题解:
法一:
动态规划。设 f[i]
表示能否到达 i
位置,那么转移方程就是:
f[i] = f[i] | f[j](0 <= j < i && j + nums[j] >= i)
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<bool> f(n);
f[0] = true;
for ( int i = 1, j; i < n; ++i ) {
for ( j = 0; j < i; ++j )
if ( f[j] && j + nums[j] >= i ) {
f[i] = true;
break;
}
if ( j == i ) return false;
}
return f[n - 1];
}
};
该版本时间复杂度为:$O(n^2)$,肯定过不了的。
可以发现,影响该版本的效率主要在第二重循环,每次都是从头开始查找第一个能到达 i
的位置,而我们可以使用一个变量 last
记录到达 i
的第一个位置,在 i+1
位置时, 0~last-1
位置不用遍历了,因为它们到不了 i
,那肯定也到不了 i+1
。所以,直接从 last
开始遍历,并且可以不使用额外数组记录状态。
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int last = 0;
for ( int i = 1; i < n; ++i ) {
while ( last < i && i > last + nums[last] ) ++last;
if ( last == i ) return false;
}
return true;
}
};
/*
时间:8ms,击败:98.55%
内存:12.5MB,击败:95.53%
*/
法二:
贪心。
用 right
表示 0~i-1
这些位置都能到达,且它们中能跳到的最远的位置。那么对于位置 i
来说:
- 若
i > right
,说明无法到达i
位置,那么肯定也无法到达n-1
位置,直接返回false
- 若
i <= right
,说明可以到达i
位置,因为在位置i
可能会跳到更远的位置,所以更新right = max(right, i + nums[i])
- 若
right >= n - 1
,说明已经能到达n-1
位置了,直接返回true
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
class Solution {
public:
bool canJump(vector<int>& nums) {
int right = 0, n = nums.size();
for ( int i = 0; i < n; ++i ) {
if ( right < i ) return false;
right = max( right, i + nums[i] );
if ( right >= n - 1 ) return true;
}
return true;
}
};
/*
时间:8ms,击败:98.55%
内存:12.4MB,击败:98.09%
*/
法三:
另外一种贪心。
问题换一个描述:我们在玩跳方格游戏,每次只能前进一个格子,消耗一个单位的能量值。每个格子上有一瓶 nums[i]
单位的能量药剂,可以选择捡或者不捡,任何时刻只能携带一瓶能量药剂,问能否到达最后一个格子。
我们可以使用 rest
记录当前还剩多少单位的能量,初始时在 0
位置,rest = nums[0]
,分情况讨论:
- 若
rest <= 0
,说明无法跳到下一个位置,直接返回false
- 否则说明能跳到下一个位置,此时面临选择能量药剂的问题,策略是:自身剩下的和格子上的,哪个大选哪个,即
rest = max(rest - 1, nums[i])
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rest = nums[0];
for ( int i = 1; i < n; ++i ) {
if ( rest <= 0 ) return false;
rest = max( rest - 1, nums[i] );
}
return true;
}
};
/*
时间:8ms,击败:98.55%
内存:12.3MB,击败:98.66%
*/