【スナップノート55】ジャンプゲーム

タイトル

非負の整数配列numsが与えられ、最初に配列の最初の下に位置します.
配列内の各要素は、その位置でジャンプできる最大長を表します.
最後の下付き文字に到達できるかどうかを判断します.
例1:

 ：nums = [2,3,1,1,4]
 ：true
 ：  1  ，  0   1,   1   3  。

例2:

 ：nums = [3,2,1,0,4]
 ：false
 ： ，  3  。  0 ，  。

ヒント:

1 <= nums.length <= 3 * 104

0 <= nums[i] <= 105

解法1(正しい)

アイデア:numsと等しい長さのboolスライスisokを設定し、アクセスした要素をtrueに設定し、numsの長さが少なくとも1であることが知られているため、nums[0]は必然的に存在し、forサイクルを利用して終了条件はi>endに設定され、初期の場合endは0であり、endを現在の遍歴状態でジャンプ可能な最も遠い下標と見なし、endの値は遍歴過程によって変化する.endが配列長を超えることができる場合、説明は最後の下付き文字にジャンプすることができる.
golangコード:

func canJump(nums []int) bool {
     
   length := len(nums)
   isok := make([]bool, length)
   isok[0] = true
   end := 0
   for i := 0; i <= end; i++ {
     
      // true
      if !isok[i] {
     
         isok[i] = true
      }
      // ， end
      if end < i+nums[i] {
     
         end = i + nums[i]
      }
      // 
      if end > length-1 {
     
         return true
      }
   }
   return isok[length-1]
}

結果:
実行結果:
実行時間:80 ms、すべてのGoコミットで15.33%のユーザーを破った
メモリ消費量:6.9 MB、すべてのGoコミットで5.78%のユーザーを破った

解法2(正しい)

アイデア:
アルゴリズム1を改良することができ、アルゴリズム1のisokは実際には余分であり、最も遠い下付きスケールに達できるかどうかを判断するためにスライスを必要としない.
golangコード:

func canJump(nums []int) bool {
     
   length := len(nums)
   end := 0
   for i := 0; i <= end; i++ {
     
      // ， end
      if end < i+nums[i] {
     
         end = i + nums[i]
      }
      // 
      if end >= length-1 {
     
         return true
      }
   }
   return false
}

結果:
パフォーマンスも向上していないようです
実行結果:
実行時間:80 ms、すべてのGoコミットで15.33%のユーザーを破った
メモリ消費量:6.9 MB、すべてのGoコミットで5.26%のユーザーを破った
公式解答:
https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/