0055._Jump_Game

发表于 分类于 ， ，

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. 每轮循环更新一次最远可达的位置——reach，reach的值为当前循环的值+当前的数组下标与之前reach值的最大值
  6. 循环终止条件：
  • 当前下标值大于可达最远位置时，代表当前下标永远达到不了
  • 可达最远位置已经大于数组长度，代表已经能跳到最后位置了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @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;
};