題目
求從陣列起始位置到達末尾所需的最小跳躍次數。
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1000- It’s guaranteed that you can reach
nums[n - 1].
解題思路
nums = [2,3,1,1,4]
jumps1 第一格的最大長度為 2, 代表最遠可以跳到索引 2
jumps2 第二格的最大長度為 3, 代表最遠可以跳到索引 4 (陣列末尾)
jumpe3 第三格的最大長度為 1, 代表最遠可以跳到索引 3
...
判斷到這就結束了, 因為第二步的時候就能跳到陣列末尾, 因此再多跳幾格下去都不會是題目要求的最小步數, 因此答案為 2- 首先需要一個變數
jumps來紀錄總共跳躍的次數 - 再來需要一個變數
current_end紀錄當前跳躍範圍內能到達的最遠位置 - 最後需要一個變數
farthest來存能到達的最遠位置，farthest就會是farthest 和目前索引能跳最遠距離取最大值farthest = Math.max(farthest, i + nums[i])。 - 當遍歷到 current_end 時(
i == current_end)代表需要再跳一次，然後更新current_end為farthest
完整程式碼
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
let jumps = 0 // 總共跳躍的次數
let current_end = 0 // 當前跳躍範圍內能到達的最遠位置
let farthest = 0 // 能到達的最遠位置
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i])
// 當遍歷到 current_end 時代表需要再跳一次
if (i == current_end) {
jumps++
current_end = farthest
}
}
return jumps
};
