当前位置: 代码迷 >> 综合 >> [leetcode] 45. Jump Game II(hard)
  详细解决方案

[leetcode] 45. Jump Game II(hard)

热度:27   发布时间:2024-01-05 01:12:36.0

原题
题意:
是Jump Game的衍生题(题解),题意求跳到最后一格所需最少步数,(默认所测数据永远可以跳到最后一格)。
思路:
利用贪心,遍历数组,记录在每一步可跳跃到的最大区域。
1.当前步数 超过已覆盖范围,则表示需要进行跳跃,同时更新已覆盖区域,可覆盖区域。
2.当前步数 在已覆盖范围内,说明无需进行跳跃,同时更新可覆盖区域。
第一步
在这里插入图片描述
在这里插入图片描述

/*** @param {number[]} nums* @return {number}*/
var jump = function (nums) {var hasCover = 0; // 当前已覆盖的区域var maxCover = 0; // 最右边可覆盖的区域var res = 0;for (let i = 0; i < nums.length; i++) {if (i > hasCover) //超过已覆盖区域 需要跳步{hasCover = maxCover;res++;if (hasCover>=nums.length) {break;}}maxCover = Math.max(maxCover, nums[i] + i);}return res;
};
  相关解决方案