JavaScript怎么解決跳躍游戲算法題

本篇內(nèi)容主要講解“JavaScript怎么解決跳躍游戲算法題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“JavaScript怎么解決跳躍游戲算法題”吧!

題目：給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)位置。

示例 1:

輸入: [2,3,1,1,4]
輸出: true
解釋: 從位置 0 到 1 跳 1 步, 然后跳 3 步到達(dá)最后一個(gè)位置。

示例 2:

輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會(huì)到達(dá)索引為 3 的位置。但該位置的最大跳躍長度是 0 ，
 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置。

通過觀察發(fā)現(xiàn)：

如果數(shù)組中不存在0，一定可以跳到最后。如果數(shù)組中存在0的情況下，要跳到最后必須滿足以下條件，從0前邊的某一個(gè)位置上開始跳躍一定能跳過這個(gè)0才可以。

例如例2中的數(shù)組，如果是以下幾種情況就可以跳到最后：

1、[4,2,1,0,4]
2、[3,3,1,0,4]
3、[3,2,2,0,4]

發(fā)現(xiàn)了什么規(guī)律呢？游戲者所在的位置的數(shù)值一定要大于0所在位置索引值與當(dāng)前位置索引值的距離差。

4>3-0;4所在的位置索引值為0,距離0的索引值相差3,4>3，所以可以跳過0，依次類推
3>3-1;
2>3-2;

找到了這道題的核心解法之后，大體思路就是，找出數(shù)組中所有0的位置，并且判斷此位置之前的所有數(shù)字是否能跳過0的位置。代碼如下：

var canJump = function(nums) {
  var canJump0List = [];

  for (var i = 0; i < nums.length - 1; ++i) {
    if (nums[i] === 0) {
//找到0所在位置,標(biāo)記為false
      var canJump0 = false;
//進(jìn)行判斷，將此位置之前數(shù)字進(jìn)行判斷,只要有一個(gè)能滿足條件就可以跳過這個(gè)0
      for (var j = i - 1; j >= 0; --j) {
// 游戲者所在的位置的數(shù)值一定要大于0所在位置索引值與當(dāng)前位置索引值的距離差           
       if (nums[j] > i - j) {
          canJump0 = true;
          break;
        }
      }
//數(shù)組中可能有多個(gè)0;所以講所有0判斷的結(jié)果放入一個(gè)數(shù)組
      canJump0List.push(canJump0);
    }
  }
//最后對(duì)數(shù)組進(jìn)行判斷,只要有一個(gè)不滿足條件返回false,即不能跳到最后
  for (var i = 0; i < canJump0List.length; ++i) {
    if (!canJump0List[i]) {
      return false;
    }
  }

  return true;
};

到此，相信大家對(duì)“JavaScript怎么解決跳躍游戲算法題”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！