0055. Jump Game
https://leetcode.com/problems/jump-game
Description
You are given an integer array nums
. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true
if you can reach the last index, or false
otherwise.
Example 1:
**Input:** nums = [2,3,1,1,4]
**Output:** true
**Explanation:** Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
**Input:** nums = [3,2,1,0,4]
**Output:** false
**Explanation:** You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 105
ac1
acepted, but ugly corner case is tedious
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 0) return false;
if (nums.length == 1) return true;
// start backwards
// meet 0, raise zeroBlock
// check current step can jump over zeroBlock, i + val > zeroBlock
int zeroBlock = -1;
for (int i = nums.length - 1 - 1; i >= 0; i--) {
if (nums[i] == 0 && zeroBlock == -1) {
zeroBlock = i;
continue;
}
if (zeroBlock == -1) continue;
if (nums[i] + i > zeroBlock) {
zeroBlock = -1;
}
}
return zeroBlock == -1;
}
}
ac2
This one is concise and beautiful.
class Solution {
public boolean canJump(int[] nums) {
int reachable = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] + i >= reachable) reachable = i;
}
return reachable == 0;
}
}
Last updated
Was this helpful?