题目描述
LC 题 - 55
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
题解
思路1:动态规划
核心点在于数组中元素为0时能否跳过
令dp[i] 表示i此时可以跳的最大步长，当遍历到某个i，dp[i]<=0时，说明无法再向前，则返回false
dp[i]的动态转移方程：dp[i] = max(nums[i],dp[i-1]-1),即当前位置i的步长和上一个位置i-1的最大步长-1两者的最大值
边界条件dp[0] = nums[0]
// OC
+ (BOOL)canJump1:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return NO;
}
int dp[n];
dp[0] = [nums[0] intValue];
if (dp[0] <= 0) {
return n==1;
}
for (int i=1; i<n; i++) {
dp[i] = MAX([nums[i] intValue], dp[i-1]-1);
if (dp[i] <= 0 && i<n-1) {
return NO;
}
}
return YES;
}
// Swift
static public func canJump1(_ nums:[Int]) -> Bool {
let n = nums.count
if n == 0 {return false}
var dp = Array(repeating: 0, count: n)
dp[0] = nums[0]
if dp[0] <= 0 {
return n==1
}
for i in 1..<n {
dp[i] = max(dp[i-1]-1, nums[i])
if dp[i] <= 0 && i<n-1 {
return false
}
}
return true
}
思路2:贪心
对于任意位置i，它所能到达的最远位置为maxRight = i + nums[i]，也就是说 对于每一个可以到达的位置x，它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。
我们依次遍历数组中的每一个位置，并实时维护能到达的最远位置maxRight,如果当前遍历的位置i<=maxRight(也就是说当前位置i可以到达)，那么我们用max(maxRight,i+nums[i])来更新最远到达位置maxRight，在遍历过程中，如果maxRight>=y(y为指定位置)，则表示y位置可以到达，返回true。如果直到遍历结束都没有maxRight>=y，则返回false
// OC
+ (BOOL)canJump2:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return NO;
}
int maxRight = 0;
for (int i=0; i<n; i++) {
if (i<=maxRight) {
maxRight = MAX([nums[i] intValue]+i, maxRight);
if (maxRight >= n-1) {
return YES;
}
}
}
return NO;
}
// Swift
static public func canJump2(_ nums:[Int]) -> Bool {
let n = nums.count
if n == 0 {return false}
var maxRight = 0
for i in 0..<n {
if i <= maxRight {
maxRight = max(maxRight, i+nums[i])
if maxRight >= n-1 {
return true
}
}
}
return false
}
思路3: 逆向遍历
如果位置i可以到达终点k点，那么逆序时k点也是可以回到i点的
令初始终点end=n-1，逆序遍历i，i从n-2到0，如果nums[i]+i>=end，则更新终点end=i，遍历结束判断终点是否为0，为0则返回true ，否则false
假设位置i,j(i<j)都可以到达终点end=k(i<j<k，nums[i]+i>=k，nums[j]+j>=k)，逆序遍历时，先遍历到j，由于nums[j]+j>=k，即从j位置可以到达k点，更新终点end=j，再遍历到i时，由于nums[i]+i>=k>j，即从i位置可以到达j，更新终点end=i。也就是说如果i点可以到达终点end，那么从终点也可以回到初始位置i
// OC
+ (BOOL)canJump3:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return NO;
}
int end = n-1;
for (int i=end-1; i>=0; i--) {
if ([nums[i] intValue] + i >= end) {
end = i;
}
}
return end == 0;
}
// Swift
static public func canJump3(_ nums:[Int]) -> Bool {
let n = nums.count
if n == 0 {return false}
var end = n-1
var i = n-2
while i>=0 {
if nums[i] + i >= end {
// 更新终点
end = i
}
i -= 1
}
return end==0
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvb8zs/
https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/
