55. Jump Game
給定一個整數數組 nums。你最初位於數組的第一個索引處，數組中的每個元素表示你在該位置的最大跳躍長度。
如果你能到達最後一個索引，返回 true；否則返回 false。
範例 1：
輸入：nums = [2,3,1,1,4] 輸出：true 解釋：從索引 0 跳躍 1 步到索引 1，然後從索引 1 跳躍 3 步到達最後一個索引。
Python
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
for i in range(len(nums)):
if i > farthest:
return false
farthest = max(farthest, i + nums[i])
return farthest >= len(nums) - 1
17.88MB, 384ms
C++
#include <vector>
#include <algorithm> // For std::max
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int farthest = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > farthest) {
return false;
}
farthest = max(farthest, i + nums[i]);
}
return farthest >= nums.size() - 1;
}
};
50.74MB, 35ms
Javascript
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let farthest = 0;
for (let i = 0; i < nums.length; i++) {
if (i > farthest) {
return false;
}
farthest = Math.max(farthest, i + nums[i]);
}
return farthest >= nums.length - 1;
};
53.9MB, 71ms
