Skip to content

Latest commit

 

History

History
68 lines (47 loc) · 1.82 KB

0055._Jump_Game.md

File metadata and controls

68 lines (47 loc) · 1.82 KB

0055. Jump Game

难度: Medium

刷题内容

原题连接

内容描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

 输入: [2,3,1,1,4]
 输出: true
 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2:

 输入: [3,2,1,0,4]
 输出: false
 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

解题方案

思路 - 时间复杂度: O(N)- 空间复杂度: O(1)******

  1. 如果数组中没有0,那么结果一定为true
  2. reach代表目前能跳到的最远位置(数组下标)
  3. 每轮循环,数组下标固定向有移动一位
  4. start代表本轮循环的位置
  5. 每轮循环更新一次最远可达的位置——reachreach的值为当前循环的值+当前的数组下标与之前reach值的最大值
  6. 循环终止条件:
  • 当前下标值大于可达最远位置时,代表当前下标永远达到不了
  • 可达最远位置已经大于数组长度,代表已经能跳到最后位置了

代码:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  let start = 0;
  let reach = 0;
  if (nums.every(i => i)) {
    return true
  }
  while (start <= reach && reach < nums.length - 1) {
    reach = Math.max(reach, nums[start] + start);
    start++;
  }
  return reach >= nums.length-1;
};