55 lines
1.5 KiB
JavaScript
55 lines
1.5 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[]} nums
|
||
* @return {number}
|
||
*/
|
||
const jump = function (nums) {
|
||
|
||
};
|
||
|
||
/*
|
||
贪心算法，从后往前找，能到达最后一个位置则表明符合要求，所以找能到达最后一个位置的所有下标最小的那个，找到这个位置之后继续找能
|
||
到达倒数第二个位置的最远的那个位置，直到发现第0个下标也符合即可
|
||
*/
|
||
|
||
function f1(nums) {
|
||
let position = nums.length - 1; // 表示需要到达的位置，初始时是数组的最后一个位置
|
||
let steps = 0; // 记录需要跳跃的步数
|
||
while (position > 0) {
|
||
for (let i = 0; i < position; i++) {
|
||
// 从左往右遍历能到达position的位置，如果找到那么这个位置就是我们要找的
|
||
if (nums[i] + i >= position) {
|
||
// 更新position
|
||
position = i;
|
||
steps++;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
return steps;
|
||
}
|
||
|
||
/**
|
||
* 贪心算法，
|
||
*
|
||
*/
|
||
|
||
function f2(nums) {
|
||
// 第一步能到达的最远位置
|
||
let maxPos = 0;
|
||
let end = 0;
|
||
let steps = 0;
|
||
// 无需遍历到最后一个元素，最后一个元素一定能被之前的某个位置跳到
|
||
for (let i = 0; i < nums.length - 1; i++) {
|
||
if (maxPos >= i) { // 更新能跳跃的最远位置
|
||
maxPos = Math.max(maxPos, i + nums[i]);
|
||
// 如果当前位置已经到达能走的最远位置，则更新下一步的边界
|
||
if (end === i) {
|
||
end = maxPos;
|
||
steps++;
|
||
}
|
||
}
|
||
}
|
||
return steps;
|
||
}
|