45. Jump Game II
給定一個長度為 n 的整數數組 nums（從0開始計數）。你最初位於 nums[0]。
每個元素 nums[i] 代表從索引 i 向前跳的最大長度。換句話說，如果你在 nums[i]，你可以跳到任何 nums[i + j]，其中：
0 <= j <= nums[i] 且 i + j < n 返回到達 nums[n - 1] 的最小跳躍次數。測試用例生成的前提是你可以到達 nums[n - 1]。
範例 1：
輸入：nums = [2,3,1,1,4] 輸出：2 解釋：到達最後一個索引的最小跳躍次數是 2。從索引 0 跳一步到索引 1，然後跳三步到最後一個索引。
Python
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
jumps = 0
current_end = 0
farthest = 0
for i in range(n - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
if current_end >= n - 1:
break
return jumps
17.41MB, 107ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return 0;
}
int jumps = 0;
int current_end = 0;
int farthest = 0;
for (int i = 0; i < n - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == current_end) {
++jumps;
current_end = farthest;
if (current_end >= n - 1) {
break;
}
}
}
return jumps;
}
};
19.08MB, 12ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
const n = nums.length;
if (n === 1) {
return 0;
}
let jumps = 0;
let currentEnd = 0;
let farthest = 0;
for (let i = 0; i < n - 1; ++i) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
jumps++;
currentEnd = farthest;
if (currentEnd >= n - 1) {
break;
}
}
}
return jumps;
};
51.36MB, 48ms
